封一
答卷编号（竞赛组委会填写）：
答卷编号（竞赛组委会填写）：
论文题目： B 题：货运公司的运输问题
参赛队员：
1. 朱远鹏 电话： 8659991
2. 贾利攀 电话： 13467517855
3. 李雯 电话： 8659991
封二
答卷编号（参赛报名号）：
答卷编号（竞赛组委会填写）：
评阅情况（评阅专家填写）：
评阅 1.
评阅 2.
评阅 3.
货运公司的运输问题
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 小时。运输车
载重运费 元/吨公里，运输车空载费用 元/公里。一个单位的原材料 A,B,C
分别毛重 4 吨、3 吨、1 吨，原材料不能拆分，为了安全，大小件同车时必须小
件在上，大件在下。卸货时必须先卸小件，而且不允许卸下来的材料再装上车，
另外必须要满足各公司当天的需求量（见图二）。
问题：1.货运公司派出运输车 6 辆，每辆车从港口出发（不定方向）后运输
途中不允许掉头，应如何调度（每辆车的运载方案，运输成本）使得运费最小。
2. 每辆车在运输途中可随时掉头，若要使得成本最小，货运公司怎
么安排车辆数？应如何调度？
3.（1）如果有载重量为 4 吨、6 吨、8 吨三种运输车，载重运费都
是 元/吨公里，空载费用分别为 ，， 元/公里，其他费用一样，又如
何安排车辆数和调度方案？
（2）当各个公司间都有或者部分有道路直接相通时，分析运输调度
的难度所在，给出你的解决问题的想法（可结合实际情况深入分析）。
（图 一）唯一的运输路线图和里程数
①
①
①
①
①
①
①
①
①
8公里
7公里
9公里
5公里
8公里
8公里
4公里
6公里
5公里港口
（图 二）各个公司对每种材料的需求量（单位/天）
各种材料的需求量（单位/天）公司
编号 A B C
① 4 1 5
① 1 5 2
① 2 0 4
① 3 1 2
① 1 2 4
① 0 4 3
① 2 2 5
① 5 3 1
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 不同材料的要求，我们再建立一个线性模型，使得这
八个公司可以从这些不同的运输方式中选择最为合适的运输方式的组合以满足
要求，然后对这些公司所选择的不同的运输方式再根据题目中每辆车每天最大的
作业时间，可以确定出在保证完成任务的情形下，所需要不同类型运输车的最少
数目。这样就可以减少指派运输车的支出，然后对不同的运输车次在途中 的运
输，都考虑其在途中是按最少经费的运输方式来运行（考虑在保证完成了本次出
车的任务后，在返回港口中时，是继续或掉头更节省经费），再结合前面的不同
运输方式的组合，就可以安排出车辆数和调度方案了。
6 模型的建立与求解
问题一的求解
首先考虑求解出满足每个公司的需求所需的最少出车次数，再在此情形下考
虑如何调度这些车次，使得整个运输作业所需的经费最少。
模型的建立与求解
根据题目中给定的各个公司对 A，B，C 三种不同的材料的需求，可以计
算出这些公司每天所需 A，B，C 三种材料的总数分别为 18 单位，18 单位，26
单位，由于每辆车的载重都是 6 吨，在假设一的前提下我们可以得出每辆车的装
载方式有如下四种方式：（a）1A+2C，（b）2B，（c）6C，（d）B+3C。我们分别
设这四种方式需要调度的次数为 C1，C2，C3，C4 这样我们就可以建立如下数
学模型：
MIN S=C1+C2+C3+C4
C1〉=18
2C2+C4〉=18
2C1+6C3+3C4〉=26 C1~~C4 为正整数；
用 LINGO 进行求解可以得到 S=27，C1=18，C2=9，C3=0，C4=0；对于这个结
果可以进一步分析可知，只需要（a）的运输方式为 13 个再加上单独运输 A 材
料的 5 车次和 9 车次（b）运输方式即可满足条件，但是这未必是最好的方式。
因为在卸货的时候必须先卸小件，而且不允许卸下来的材料再装上车，所以对某
些公司来说，如公司（1）通过分析可以知道用装载方式（a）和（b）及单独运
输 A 的
图三
方式进行运载不能满足公司一的条件，还需要 A+C 这种方式。那么究竟需要运
载方式（1），（2）及 A 和 A+C 的方式多少个才合适呢，我们不妨以全是顺时针
的方式来进行考虑，比如对于公司（1）需要 2 个（a）的运输方式，1 个（b）
的运输方式和一个单独运输 A 方式。如图三，按顺时针方式对每个公司进行综
合的考虑可以得到需要方式（a）12 个，运输 A+C 方式 2 个，单独运输 A 方式
4 个以及方式（b）9 个可以较好的满足体设条件。对这些运输方式，分别记顺时
针的调用车次序为 i0（i0=1~27），其中 i=1~12 为调用方式（a），i=13~14 为调用
方式 A+C，i=15~18 为调用方式 A，i=19~17 为调用方式（b）；逆时针的调用车
次序为 i1（i1=1~27），其中 i=1~4 为调用方式 A，i=5~6 为调用方式 A+C，i=7~18
为调用方式（a），i=19~27 为调用方式（b）。对于每个被调用以满足不用公司要
求 的 车 次 ， 由 于 不 考 虑 掉 头 ， 故 可 以 得 到 其 运 输 所 需 要 的 经 费 为 Pij= ∑
（*Sij+*sj0）（i=1~27，j=0 或 1），其中 w 为运输车的载重，Sij 为所运载
的 区 间 的 路 程 ， Sj0 则 表 示 空 车 回 到 港 口 的 距 离 ， 总 费 用 为 ： P= ∑
Pij+S*10+20*K，其中 K 为所调用的车辆的个数；其中 Pij 的计算所得的结果参
看表（1），表（2）中列出各个公司所需的材料是由哪些车次所负责运输的。根
据这两个表中的数据设 Xij（其中 i=1~27，j=0 或 1）为第 i 辆列车的调度情况：
其中 Xi0=1 表示第 i 辆车次采用顺时针运行，Xi0=0 则表示不采用第 i 辆车次顺
时针运输，Xi1=1 则表示第 i 辆车采用逆时针运输，Xi1=0 表示第 i 辆车不采用
顺时针运输。由上可以对这个问题建立一个 0-1 规划模型：
Min ∑Pij*Xij
∑ Xij〉=27
x10+x181=1;x20+x171=1;x130+x61=1; x150+x151=1;
（对于公司（1）两种不同运输方式中只能选择一种）
………. （其他公司的处理方法一样，其中如：x141-x151=0，这是说明如过采
用 141，则也采用 151 的车次，其他各处同理）
Xij=0 或 1
结论：
对上 0-1 模型，代入数据，用 Lingo 求解可得∑Pij=，又由于 S=27，
K=6，所以总费用为 P=（元），其中所调用的车次以及每个车次的所花的
经费参见表（3），对于所得的结果，由于车的速度为 60 公里/时，那么每辆车运
行一周回到港口刚好需要 1 小时，而现在需要共需要转 27 圈，又每辆车的每天
的工作时间是 8 小时，所以这 6 辆车一天的能力是运转 48 圈，所以即使再考虑
装载时间和卸货时间所得结果也是合理的。
问题二的求解
问题二中的车辆可以掉头，但是这只会影响每辆车在运行过程中空车运行回
港口的路费，所以求解的模型和第一问中的模型是一样的，只不过这时候的 Pij
已经有所变化，这时候的 Pij 的求解是这样计算的：在每辆车完成了该车的装载
任务后，看所处的位置在何处，如果掉头回港口更近的话，则掉头，否则继续前
进，其他的计算方式则和第一问中的一样，具体的计算结果参见表（4）；
结论：
仍然使用 Lingo 进行求解，可以得到这时候的∑Pij=，这时候 S 仍为
27，而 K 的确定是这样的：把所有车次的时间按时间公式∑（t0+t1+t2），求出总
的时间为：1711 分钟。每一辆车的最大工作时间为：60*8=480 分钟，粗略计算，
需车数：1711/480≈4 辆，
综合考虑装载和卸货时间用的时间，这个值也是合理的。那么这时的总费
用 P=（元），
6．3 问题三的求解
以尽可能装满车为原则，4，6，8 吨三种车型有以下装法，并编好序。每
辆车尽可能一次性卸完分析出每个公司所需车次。
4 吨（车型） 6 吨 8 吨
Y1=B+C Y4=2B Y8=2A
Y2=A Y5=A+2C Y9=A+4C
Y3=4CX6=6CX10=A+B+C
Y7=B+3C Y11=8C
Y15=B+C Y12=2B+2C
Y16=B+2C Y13=B+5C
Y14=B+A
Y17=B+4C
对于每个公司的需求我们都是考虑尽可能用上面给出的不同的装载方式来满足，
可建立模型如下：
Min ∑Yi
ST
Y2+Y5+2Y8+Y9+Y14=Gn1
Y1+2Y4+Y7+Y15+Y16+Y11+2Y12+Y13+Y14+Y17=Gn2
4Y3+2Y5+3Y7+Y15+2Y16+4Y9+8Y11+2Y12+5Y13+4Y17=Gn3
Yi 是正整数
其中 Gni（n=1—8，i=1，2，3）表示第 n 个公司分别对 A，B，C 产品的需求
量。代入用 Lingo 求解可以得出下表
现对上表分析，车辆数：
考虑到增加车辆有 20 元的增加费用，车辆越少越好。但必须在规定时间内（8
小时），完成一定车次的任务。
按时间计算公式:
Σ（t0+t1+t2）
(t0—装载时间，t1—路途行程时间，t2—卸载时间)
公司
（需求）
1．
（4，1，5）
2．
（1，5，2）
3．
（2，0，4）
4．
（3，1，2）
5．
（1，2，4）
6．
（0，4，3）
7．
（2，2，5）
8．
（5，3，
1）
车次 2Y8+X1
3
Y4+Y14
+Y12
2Y5 Y2+Y5+
Y14
Y4+Y9 Y4+Y15
+Y16
Y9+Y14
+Y15
Y8+Y1
0+2Y1
4
求出三种车所用时间分别为：
4 吨：83 分钟 6 吨：567 分钟 8 吨：621 分钟
一辆车的最大工作时间为：8*60=480（分钟）。
易知所需车数为：1+2+2=5（辆）
按运费计算公式:
求出完成一天任务的总运费为： 元。
考虑到，4 吨车只用了一次，可加开一次 6 吨车代替，以减少费用。事实证明 6
吨车加开一次时间是完全允许的，可节约费用：
20-（0．）*24=（元）。
那么车辆数变为：4 辆;费用： 元。
7．参考文献
[1] 徐玖平，胡知能，王委，运筹学，科学出版社，2004
[2] 姜启源，数学模型，高等教育出版社，2003
[3] 谢金星，薛毅，优化建模与 LINDO/LINGO 软件，2005
附录
附表一
经费
车次 i Pij
0 1
1 58
2 58
3 180 58
4 58
5 67
6
7
8
9
10
11
12
13
14 596
15
16
17
18 398
19 142．2 76
20 106 180
21 138．4 180
22 180 365．6
23 220 448．8
24 303．2 492
25 492 512
26 492 563．6
27 271 596
附表二
经费
车次 i Pij
0 1
1 58
2 58
3 180 58
4 58
5 67
6
7
8
9
10
11
12
13 92．8
14
15
16
17
18
19 76
20 106 180
21 180
22
23 448．8
24
25
26
27
附表三
A 的满足 B 的满足 C 的满足公司
顺时针 逆时针 顺时针 逆时针 顺时针 逆时针
1 10 20
130 150
161 171
181 61
190 271 10 20
130
171 181
61
2 30 151 190
200
210
251
261
271
30 161
3 40 50 131 141 40 50 141 151
4 60
160 170
101
111 121
220 241 60 131
5 70 91 220 230 231 241 70 80 111 121
6 230 240
250
211 221
231
90 110 91 101
7 80 90 71 81 250 260 201 211 100 110
120
71 81
91
8 100 110
120 140
180
11 21
31 41
51
260 270 191 201 140 51
附表四
经费
车次 i Pij
0 1
1 89．6 38
2 89．6 38
3 168 38
4 268．8 38
5 268．8 47
6 324．8
7 408．8 123．2
8 476 123．2
9 519．2
10 567．2
11
12
13 75．2
14 596
15 60．8
16
17 220．4
18 398
19 48．6 56
20 168 90．8
21 168 146．4
22 365．6 168
23 448．8 214．4
24 492 303．2
25 512 492
26 563．6 492
27 596 527
附表五
经费
车次 i Pij
0 1
1 89．6 38
2 89．6 38
3 168 38
4 38
5 47
6
7 123．2
8 123．2
9
10
11
12
13 75．2
14
15
16
17
18
19 48．6 56
20 168 90．8
21 168 146．4
22 168
23 214．4
24 303．2
25
26
27
LINGO 代码一
Model:
min=*x10+*x20+180*x30+*x40+*x50+*x60+*x70
+*x80+*x90+*x100+*x110+*x120+*x130+596*x14
0+*x150+*x160+*x170+398*x180+58*x11+58*x21+58*x31+58*x4
1+67*x51+*x61+*x71+*x81+*x91+*x101+*x111+
*x121+*x131+*x141+*x151+*x161+*x171+
*x181+76*x190+*x191+106*x200+180*x201+*x210+180*x211+180*x2
20+*x221+220*x230+*x231+*x240+492*x241+492*x250+512*x2
51+492*x260+*x261+527*x270+596*x271;
x10+x20+x30+x40+x50+x60+x70+x80+x90+x100+x110+x120+x130+x140+x150+x
160+x170+x180+x11+x21+x31+x41+x51+x61+x71+x81+x91+x101+x111+x121+x1
31+x141+x151+x161+x171+x181+x190+x191+x200+x201+x210+x211+x220+x221
+x231+x231+x240+x241+x250+x251+x260+x261+x270+x271>=27;
x10+x181=1;x20+x171=1;
x130+x61=1;
x150+x151=1;
x30+x161=1;
x141-x151=0; x40+x141=1;
x50-x40=0;
x131-x141=0;
x101-x131=0;
x111-x131=0;
x121-x131=0;
x60+x131=1;
x101-x131=0;
x111-x131=0;
x121-x131=0;
x60-x160=0;
x60-x170=0;
x70+x91=1;
x70-x80=0;
x91-x111=0;
x91-x121=0;
x101-x91=0;
x90+x81=1;
x90-x110=0;
x100-x110=0;
x120-x110=0;
x71-x91=0;
x81-x91=0;
x80-x90=0;
x140+x11=1;
x100-x140=0;
x110-x140=0;
x120-x140=0;
x180-x140=0;
x11-x51=0;
x21-x51=0;
x31-x51=0;
x140+x51=1;
x41-x51=0;
x21-x51=0;
x31-x51=0;
x41-x51=0;
x190+x271=1;
x200+x261=1;
x210+x251=1;
x220+x241=1;
x230+x231=1;
x240+x221=1;
x250+x211=1;
x260+x201=1;
x270+x191=1;
@BIN(x10);@BIN(X11);@BIN(X20);
@BIN(X21);@BIN(X30);@BIN(X31);
@BIN(X40);@BIN(X41);@BIN(X50);
@BIN(X51);@BIN(X60);@BIN(X61);
@BIN(X70);@BIN(X71);@BIN(X80);
@BIN(X81);@BIN(X90);@BIN(X91);
@BIN(x100);@BIN(X101);@BIN(X110);
@BIN(X111);@BIN(X120);@BIN(X121);
@BIN(X130);@BIN(X131);@BIN(X140);
@BIN(X141);@BIN(X150);@BIN(X151);
@BIN(X160);@BIN(X161);@BIN(X170);
@BIN(X171);@BIN(X180);@BIN(X181);
@BIN(x190);@BIN(X191);@BIN(X200);
@BIN(X201);@BIN(X210);@BIN(X211);
@BIN(X220);@BIN(X221);@BIN(X230);
@BIN(X231);@BIN(X240);@BIN(X241);
@BIN(X250);@BIN(X251);@BIN(X260);
@BIN(X261);@BIN(X270);@BIN(X271);
end
LINGO 代码二
Model:
min=*x10+*x20+168*x30+*x40+*x50+*x60+*x70+4
76*x80+*x90+*x100+*x110+*x120+*x130+596*x140+6
*x150+*x160+*x170+398*x180+38*x11+38*x21+38*x31+38*x41+4
7*x51+*x61+*x71+*x81+*x91+*x101+*x111+317
.6*x121+*x131+*x141+*x151+*x161+*x171+*x1
81+*x190+56*x191+168*x200+*x201+168*x210+*x211+*x220
+168*x221+*x230+*x231+492*x240+*x241+512*x250+492*x251
+*x260+492*x261+596*x270+527*x271;
x10+x20+x30+x40+x50+x60+x70+x80+x90+x100+x110+x120+x130+x140+x150+x
160+x170+x180+x11+x21+x31+x41+x51+x61+x71+x81+x91+x101+x111+x121+x1
31+x141+x151+x161+x171+x181+x190+x191+x200+x201+x210+x211+x220+x221
+x231+x231+x240+x241+x250+x251+x260+x261+x270+x271>=27;
x10+x181=1;x20+x171=1;
x130+x61=1;
x150+x151=1;
x30+x161=1;
x141-x151=0; x40+x141=1;
x50-x40=0;
x131-x141=0;
x101-x131=0;
x111-x131=0;
x121-x131=0;
x60+x131=1;
x101-x131=0;
x111-x131=0;
x121-x131=0;
x60-x160=0;
x60-x170=0;
x70+x91=1;
x70-x80=0;
x91-x111=0;
x91-x121=0;
x101-x91=0;
x90+x81=1;
x90-x110=0;
x100-x110=0;
x120-x110=0;
x71-x91=0;
x81-x91=0;
x80-x90=0;
x140+x11=1;
x100-x140=0;
x110-x140=0;
x120-x140=0;
x180-x140=0;
x11-x51=0;
x21-x51=0;
x31-x51=0;
x140+x51=1;
x41-x51=0;
x21-x51=0;
x31-x51=0;
x41-x51=0;
x190+x271=1;
x200+x261=1;
x210+x251=1;
x220+x241=1;
x230+x231=1;
x240+x221=1;
x250+x211=1;
x260+x201=1;
x270+x191=1;
@BIN(x10);@BIN(X11);@BIN(X20);
@BIN(X21);@BIN(X30);@BIN(X31);
@BIN(X40);@BIN(X41);@BIN(X50);
@BIN(X51);@BIN(X60);@BIN(X61);
@BIN(X70);@BIN(X71);@BIN(X80);
@BIN(X81);@BIN(X90);@BIN(X91);
@BIN(x100);@BIN(X101);@BIN(X110);
@BIN(X111);@BIN(X120);@BIN(X121);
@BIN(X130);@BIN(X131);@BIN(X140);
@BIN(X141);@BIN(X150);@BIN(X151);
@BIN(X160);@BIN(X161);@BIN(X170);
@BIN(X171);@BIN(X180);@BIN(X181);
@BIN(x190);@BIN(X191);@BIN(X200);
@BIN(X201);@BIN(X210);@BIN(X211);
@BIN(X220);@BIN(X221);@BIN(X230);
@BIN(X231);@BIN(X240);@BIN(X241);
@BIN(X250);@BIN(X251);@BIN(X260);
@BIN(X261);@BIN(X270);@BIN(X271);
end
