货运公司的运输问题

这是网络上出现的关于货运公司的运输问题讨论，是目前高校物流专业毕业论文话题，内容涉及广泛，线性规划模型、减小运输成本考量……等等，下面是针对该问题的详细解决方案。

1 摘要

本文根据货运公司需要完成的运输量和确定的运输路线图，对货运公司的出车调度方案进行分析和优化，分别建立了线性规划模型和0-1规划模型，解决了车辆安排问题，得出了运费最小的调度方案。

首先，由于每次出车的出车成本费是固定的，为了减小运输成本，就要减少出车次数，但同时又要满足各公司对材料的需求，以公司需求为约束条件，以最小出车数为目标函数，建立一个线性规划模型，并用Lingo求解，得出了最少出车次数为27辆。进一步考虑运输车调度问题，由于出车方向不定，分为逆时针和顺时针两种情况，而且这两种情况是非此即彼的对立关系，故建立了一个0-1规划模型，0表示顺时针行驶，1表示逆时针行驶，采用Lingo求解，得出了运输车在运输途中不允许掉头的调度方案（见表一）。

问题二中允许运输车掉头只会影响运输车卸货后空载的行驶路程，也即运输车的空载费用，故通过修改目标函数中的相关系数，仍然建立线性规划模型和0-1规划模型，采用Lingo求解，得出需要安排的运输车为3辆，运输途中允许掉头的调度方案见表二。

问题三中增加了运输车的种类，并区分了运输车空载时的运费，由于运输车装载材料的方式有很多种，在上面分析的基础上，增加约束条件，得出一种新的线性规划模型，通过Lingo解得需要安排的车辆数为5辆，调度方案见表三。第（2）小问中，考虑部分公司有道路相通，采用Dijkstra算法来解决这类最短路问题。

关键字：线性规划模型，0-1规划模型，Dijkstra算法

2 问题重述

某地区有8个公司（如图一编号①至⑧），某天某货运公司要派车将各公司所需的三种原材料A,B,C从某港口（编号⑨）分别运往各个公司。路线是唯一的双向道路（如图一）。货运公司现有一种载重 6吨的运输车，派车有固定成本20元/辆，从港口出车有固定成本为10元/车次（车辆每出动一次为一车次）。每辆车平均需要用15分钟的时间装车，到每个公司卸车时间平均为10分钟，运输车平均速度为60公里／小时（不考虑塞车现象），每日工作不超过8小时。运输车载重运费1.8元/吨公里，运输车空载费用0.4元/公里。一个单位的原材料A,B,C分别毛重4吨、3吨、1吨，原材料不能拆分，为了安全，大小件同车时必须小件在上，大件在下。卸货时必须先卸小件，而且不允许卸下来的材料再装上车，另外必须要满足各公司当天的需求量（见图二）。

问题：1.货运公司派出运输车6辆，每辆车从港口出发（不定方向）后运输途中不允许掉头，应如何调度（每辆车的运载方案，运输成本）使得运费最小。

2. 每辆车在运输途中可随时掉头，若要使得成本最小，货运公司怎么安排车辆数？应如何调度？

3.（1）如果有载重量为4吨、6吨、8吨三种运输车，载重运费都是1.8元/吨公里，空载费用分别为0.2，0.4，0.7元/公里，其他费用一样，又如何安排车辆数和调度方案？

（2）当各个公司间都有或者部分有道路直接相通时，分析运输调度的难度所在，给出你的解决问题的想法（可结合实际情况深入分析）。

（图 一）唯一的运输路线图和里程数

（图 二）各个公司对每种材料的需求量（单位/天）

3 模型假设

1．假设每辆车装载时发挥其最大的装载能力；

2．假设货运公司都是先考虑节省人力和出车次数最少的情况下再考虑如何安排运输方式以减少经费支出；

3．假设运输车行驶过程中不考虑塞车抛锚现象，以保证每辆车每天可以达到最大的作业时间。

4 符号说明

C1  一单位A材料和二单位C材料的装载方式；

C2  二单位B材料的装载方式；

C3  六单位C材料的装载方式；

C4  一单位B材料和三单位C材料的装载方式；

Pij 被调用车的运输经费；

Sij 所运载的区间的路程；

Xij 第i辆列车的调度情况；

Xi0=1表示第i辆车采用顺时针运输；

Xi0=0表示第i辆车不采用顺时针运输；

Xi1=1表示第i辆车采用逆时针运输；

Xi1=0表示第i辆车不采用顺时针运输；

t0  装载时间；

t1  路途行程时间；

t2  卸载时间；

Gni（n=1—8，i=1，2，3）表示第n个公司分别对A，B，C产品的需求量；

5 问题分析

对于这个货运公司的运输问题，问题一中给出了6辆可以使用的运输车，根据各公司对材料的需求，这6辆车必然会被反复的调用。要减少运输经费，首先要减少出车的次数，但是究竟要出车几次才可以满足公司对材料的需求呢？由于每辆车只能装载6吨的货物，所以每辆车的装载方案有： 6个C，2个B， 1个A 2个C，1个B 3个C四种（每次出车都优先考虑发挥每辆运输车最大的装载能力），这样再根据八个公司对A，B，C三种材料总的需求量就可以建立一个线性规划模型求出出车的最少次数S。在满足最少出车次数S的前提下，还要考虑运输车的调度问题，由于出车方向不定，分为逆时针和顺时针两种情况，而且这两种情况是非此即彼的对立关系，这属于0-1规划问题，解决的方法是令Xi0等于1表示采用第i辆车次按顺时针来运行，Xi0等于0表示不采用第i辆车次顺时针运行。Xi1等于1表示采用第i辆车次逆时针运行，等于0表示不采用这辆车次逆时针运行，再结合题目中的其他相关数据便可以建立一个0-1规划模型求解。 问题二中的解决方法和第一问中的解决方法是一样的，不过由于这时候运输车可以掉头，故可以减少由于运输车在途中空载的路程，而这只会影响模型中目标函数的中的价值系数的改变，其他和第一问的求解方法是一致的。在第三问中给出了三种不同的运输车，对于这三辆不同的运输车，每次出车时可以用来装载不同单位的A，B，C材料（这时我们不像第一问那样来考虑，每次出车可以不装载完每辆车），对于这三种不同的运输车可以得出很多不同的装载方式，比如对于装载量为8吨的运输车，可以为每次装载2个A或者1个A和B等。根据每个公司对A，B，C不同材料的要求，我们再建立一个线性模型，使得这八个公司可以从这些不同的运输方式中选择最为合适的运输方式的组合以满足要求，然后对这些公司所选择的不同的运输方式再根据题目中每辆车每天最大的作业时间，可以确定出在保证完成任务的情形下，所需要不同类型运输车的最少数目。这样就可以减少指派运输车的支出，然后对不同的运输车次在途中 的运输，都考虑其在途中是按最少经费的运输方式来运行（考虑在保证完成了本次出车的任务后，在返回港口中时，是继续或掉头更节省经费），再结合前面的不同运输方式的组合，就可以安排出车辆数和调度方案了。