运输课程设计.doc

山东交通学院《运输工程》课程设计
摘 要
目前，现代物流产业已经是覆盖整个产业链的、全方位的、立体化的服务供应商，国家和企业也越来越重视物流在国民经济中的重要地位。现代物流被看作是降低资源消耗、提高人力素质之后的“第三利润源” 。在物流领域中，车辆行驶路线选择始终是一个重要的组成部分, 特别是在最近几十年中，许多学者都对其进行了大量的实验和研究。本文首先介绍了车辆路径问题的产生背景及定义，然后由此引出并介绍了车辆行驶路线的类型，以及行驶路线的选择和优化方法，并针对汇集式行驶路线的启发式算法进行了实例分析。
关键词：车辆行驶路线，优化，启发式算法

目 录
1车辆路径问题的产生背景 3
2车辆路径问题的定义 3
3车辆行驶路线的类型 3
3.1往复式行驶路线 3
3.2环形式行驶路线 3
3.3汇集式行驶路线 4
4车辆行驶路线的选择和优化 4
4.1环形式行驶路线的选择 4
4.1.1 环形式行驶路线的优选标准 4
4.1.2数学模型 4
4.2 汇集式行驶路线的启发式算法 5
4.2.1启发式算法概述 5
4.2.2启发式算法求解流程 5
4.2.3启发式算法实例分析 7
5结论及设计体会 10
参考文献 11

1车辆路径问题
1．1车辆路径问题的产生背景
美国物流管理学会(Council of Logistics Management，CLM)对物流所作的定义为：“为符合顾客的需要，对原料、制造过程中的存货与制成品以及相关信息，从其起运点至最终消费点之间，做出的追求效率与成本效果的计划、执行与控制过程。” 而有关资料显示，物流配送过程(包含仓储、分拣、运输等)的成本构成中，运输成本占到52%之多。因此，如何在满足客户适当满意度的前提下，将配送的运输成本合理地降低，成为一个紧迫而重要的研究课题，车辆路径问题正是基于这一需求而产生的。
1.2车辆路径问题的定义
车辆路径问题可以描述为：给定一组有容量限制的车辆的集合、一个物流中心（或供货地）、若干有供货需求的客户，组织适当的行车路线，使车辆有序地通过所有的客户，在满足一定的约束条件（如需求量、服务时间限制、车辆容量限制、行驶里程限制等）下，达到一定的目标（如路程最短、费用极小、时间尽量少、使用车辆数尽量少等）。
因此研究车辆路径问题，就是要研究如何安排运输车辆的行驶路线，使运输车辆依照最短的行驶路线或最短的时间费用，依次服务于每个客户后返回起点，总的运输成本实现最小。
2车辆行驶路线的类型
2.1往复式行驶路线
往复式行驶路线，是指运输过程中车辆在某一运输路线的两个端点之间做多次（包括一次）往复行驶的路线类型。它又可以分成三种形式：单程有载往复式、回程部分有载往复式和双程有载往复式。
2.2环形式行驶路线
环形式行驶路线是指车辆在由若干个装卸作业点组成的一条封闭回路上，作连续单向运行的行驶路线。由于各货运点在运输方向上的相互位置不同，这种形式的路线分为三种形式，即简单环式、交叉或三角环式以及复合环式。
2.3汇集式行驶路线
汇集式行驶路线是指车辆沿着分布于运行路线上各装卸作业点，依次完成相应的装卸作业，且每运次的货物装（卸）量均小于该车额定载质量，直到整个车辆装满（或卸空）后返回出发点的行驶路线。般情况下，汇集式路线为封闭路线。车辆可能沿着一条环形式的路线行驶，也可能在一条直线形路线上往返行驶。
　　汇集式的运输形式一般可分为三种形式：（1）分送式：车辆从起点装车完成后，沿着运行路线上的各个货运点依次进行卸货，最终可返回起点；（2）收集式：车辆从起点空车出发，沿着运行路线上的各个货运点进行装货，最终达到目的地；（3）分送——收集式：车辆沿着运行路线上的各个货运点分别或者同时进行装货以及卸货。
当车辆采用汇集式行驶路线完成运输任务时，每次周转的货物周转量的大小与车辆沿路线上各货运点的绕行次序有关。若绕行次序不同，即使完成同样货运任务其周转量也不一样。在这种情况下，按总行程最短组织车辆进行运输最为经济。
3车辆行驶路线的选择和优化
3.1环形式行驶路线的选择
3.1.1 环形式行驶路线的优选标准
选择环形式行驶路线的原则是：当完成同样货运任务时，里程利用率β最高为最佳。环形式行驶路线以运次为基本运输过程进行组织，并且在一条环形路线上包含有多个运次、多项货运任务。其中，每个运次的重车路线由货运任务决定，所以重车方向是一定的，无从选择。那么，只有合理组织该环形路线各个运次的衔接顺序，使总空车行程最短，才能使里程利用率β最高，才能获得最经济的行驶路线。
3.1.2数学模型
假设m为空车发点数（包括卸货点和车场），n为空车收点数（包括装货点和车场），Qij为由第i点发往第j点的空车数，qj为第j点所需空车数，Qi为第i点发出空车数，Lij为第i点到第j点的距离，则其空车行驶路线的选择问题的数学模型如下：
目标函数是以全部车辆的总空车里程LV最短为求解目标，即
minLV=
约束条件：=Qi (i=1,2,…,m) =qj (j=1,2,…,n)
Qij >=0
3.2 汇集式行驶路线的启发式算法
3.2.1启发式算法概述
汇集式行驶路线的优选原则是以每周转的总行程最短为最优。
可将此问题归为运筹学中的货郎担问题，应用启发式算法来进行近似求解，其基本思路是：当货运点多，总运量较大、需用运输车辆超过一辆时，选择汇集式行驶路线首先根据运输车辆每车次最高装载量定额，按就近调车的原则对货运点进行分组；然后按总行程最短的原则，采用启发式算法分别确定每车沿其本组货运点的绕行次序，以选定单车运行路线。
3.2.2启发式算法求解流程
首先确定计算所需数据，其中包括:货运点的分布图或货运点间里程矩阵Lij；货运点收（卸）货量（qj）； 单车最高装载量（qH）。 其中，i、j 为货运点序号，qj 、qH 的计算单位视货物情况而定，如可以是吨、件、桶、箱、瓶等。
A :确定货运点分组数d ：d=［Σqj/qH+0.5］
B :单车货运点分组：
其程序为:
1）确定单车行驶路线序号N（N=1，2 ，…d），即单车货运点分组组别序列，以依次确定单车行驶路线。
2) 选择第一个收货点。以K表示收货点的序号，即选择K=1的收货点。
首先确定距发货点（j=0）最远的收货点（j = r）为第一个收货点，即确定maxLoj及车辆实际载质量q=qj ,并将该点记为NK = N1，即第N组单车行驶路线上的第一个收货点。此时第j 收货点已收到所需数量（qj）的货物，不再参加后续单车行驶路线上收货点的分组选择，再令i=j ，继续选择下一个收货点。
3）选择其余收货点。即按照就近选点的原则，选取距上一个收货点（i=j=r）最近的第j（j ≠r）收货点为第K+1个收货点，此时车辆实际载质量增加至q=q+qj ；将该点记为Nk（k=k+1）。
如果q＜qH，则表明车辆载质量没有充分利用，若尚有qj ≠0 ，则继续选择本组下一个收货点；如果q=qH，表明本组单行驶路线上的全部货运点已选择完毕，转本程序第（1）步骤，进行第N+1组单车货运点的选择；如果q＞qH，表示车辆实际装载量已超过车辆的每车次的最高装载定额，不能再负担第K+1个收货点的送货任务所以本组单车行驶路线的全部收货点为K个，并按选点的先后顺序初排货运点序列NK，然后转本程序步骤（1）进行下一组货运点的选择。若全部货运点的qj=0，则表明本方案（S）的全部收货点选择完毕，据此，初排本组货运序列。若还有其它货运点分组方案，则转本程序第（1）步继续选择下一组别N+1的货运点，直至S=e 方案分组完毕，则转下一程序C。
C ：选择单车货运点绕行次序。
1)列出本组各货运点间里程（Lih）统计表，如表4-1所示。表内各点按初排货运点顺序排列，包括收、发货点。
表4-1
Nk
Nk i h
N0
N1
N2
…
Nm
0
1
2
…
m
N0
0
0
L0,1
L0,2
…
L0,m
N1
1
L1,0
0
L1,2
…
L0,m
N2
2
L2,0
L2,1
0
…
L2,m
…
…
…
…
…
…
…
Nm
m
Lm,0
Lm,1
Lm,2
…
0

2) 按Nk序列,选取前两个货运点(假定其序号分别为a 、b)与发货点（j =0）组成初选循环回路，记为0—a—b—0 。按Nk序列,选取前两个货运点，组成初选循环回路。
3) 按Nk序列，依次选取货运点XK 插入初选循环回路。其插入原则是：回路中因包含了货运点X（XK）而使行驶路线长度的增加值（△ih）最小为最优。即 △ih=Li,x+Lx,h-Li,h=min
4) 计算本组货运点绕行里程LN
LN=
5) 依次确定下一组（第N+1组）单车货运点的绕行次序，直到各组货运点绕行次序全部确定完毕（N=d）。然后求本方案各组绕行里程合计∑LN。

6) 如果还有其它货运点分组方案（即S＞1），则就要重复上述各步，选定该方案单车绕行次序，直到全部方案(S=e)的单车货运点的绕行次序都确定为止。
最后，从所有方案中选择总绕行里程最短（即S ：∑LN =min ）的方案。
3.2.3启发式算法实例分析
某牛奶厂，拟采用一辆中型载重车（q=10吨）将鲜奶配送给6个固定的牛奶销售点，要求采用启发式法选择车辆绕行次序，目标是在完成任务的前提下，绕行的总里程最短。
表4-2 各点之间的里程表
Bj
Bi
B0
B1
B2
B3
B4
B5
B6
B0
0
8
11
10
7
9
12
B1

0
9
5
6
10
8
B2

0
6
4
6
9
B3

0
4
7
6
B4

0
12
10
B5

0
11
B6

0
表4- 3各牛奶销售点的需求表
销售点
B1
B2
B3
B4
B5
B6
需求（吨）
4
3
5
2
2
2
解：（1）程序A：计算货运点的分组数d,即
d=［Σqj/qH+0.5］=[(4+3+5+2+2+2)/10+0.5]=2
(2)程序B:进行单车货运点分组。
①确定第一组的第一个送货点，即距离B0最远的送货点，根据各点之间的里程表可以确定第一个点是B6,其距离B0为12，并检查车辆是否已经装满，此时车辆装载的货物为2吨，车辆未达到满载.
②确定第一组的第二个送货点，此时应选择距离B6最近的送货点，也就是B3,此时B3距离B6最近，其最近距离为6，此时车辆装载了2+5=7吨货物，车辆未达到满载，第一辆车还可以继续装载货物.
③确定第一组的第三个送货点，此时距离第三个送货点最近的是B4,最近距离为4，检查车辆是否达到满载，此时车辆装载的货物为2+5+2=9吨，还差一吨就会满载，但是其他的送货点所需求的送货量都超过了1吨，所以第一辆车的装载完成，运输路线也已经确定，接下来只需要选择此车的下一次绕行路线就可以了。
④重复第二步的做法，选出此车的下一次运输路线，首先排除已经选择好了的点，选择距离B0最远的点B2,此时B2距离B0最远，为11，并检查车辆装载率，此时车辆装载的货物为3吨，未达到满载，所以这辆车可以继续装载货物。
⑤选择第二辆车的第二个送货点，距离B2最近的B5,距离为6，检查车辆装载率，此时车辆装载的货物为3+2=5吨，未达到满载，可以继续装载货物。
⑥第二辆车最后一个送货点为B1，此是车辆装载的货物为3+2+4=9吨，车辆运输安排完毕。
得出货运点分组方案如表4-4
表4-4 货运点分组方案统计表
方案S
组别N
初排货运点序列j
Ⅰ
1
6 ，3 ，4
2
2 ，5 ，1
(3)程序C：选择单车货运点绕行次序。
组别1：初选循环回路：0-6-3-0
插入货运点4后的循环回路情况有：0-4-6-3-0 △ih =5；
0-6-4-3-0 △ih =8；
0-6-3-4-0 △ih =1；
因为行驶路线增加值最小为1，所以应选择循环回路0-6-3-4-0
此时单车绕行里程为29.
组别2：初选循环回路：0-2-5-0
插入货运点1后的循环回路情况有：0-1-2-5-0 △ih =6；
0-2-1-5-0 △ih =13；
0-2-5-1-0 △ih =9；
因为行驶路线增加值最小为6，所以应选择循环回路0-1-2-5-0
此时单车绕行里程为32.

结果如表4-5

表4-5
方案S
组别N
单车绕行路线
单车绕行里程
绕行里程合计
Ⅰ
1
0-6-3-4-0
29
61
2
0-1-2-5-0
32
由于此题只有方案Ⅰ一种方案，所以此方案即为本题的最佳单车绕行路线方案，单车绕行里程合计为61。
4结论及设计体会
在物流快速发展的大背景下,正确合理地安排车辆的运行线路，实现合理的线路运输，可以有效地节约运输时间，增加车辆利用率，从而降低运输成本，提高企业经济效益与客户服务水平，使企业达到科学化的物流管理, 这也是企业提高自身竞争力的有效途径之一。
通过此次课程设计，我明白了车辆运行线路的优化对物流的重要性，不仅知道了车辆行驶线路的类型，更是学习到并掌握了一些运行线路的优化方法，总之，这次课程设计让我受益匪浅。

参考文献
[1]胡思继.交通运输学[M].北京：人民交通出版社，2001.
[2]陈京.汽车运输组织管理[M].北京：机械工业出版社，2004
[3]王之泰.现代物流学[M].北京：中国物资出版社，2001
[4]杨兆升.智能运输系统概论[M].北京：人民交通出版社，2003
[5]孙媛.企业物流网络规划研究.同济大学学位论文，2008
[6]李静.基于道路网络影响的物流运输成本研究.合肥工业大学学位论文，2009
[7]朱金玉.现代物流基础[M].北京：中国物资出版社，2003
[8] 郭耀煌，李军．满载问题的车辆路线安排[J]．系统工程学报，1995，10(2)：106-118
[9]郭耀煌，李军．车辆优化调度问题的研究现状述评哪．茜南交通人学学报，1995，30(4)：376—382
[10]李军．车辆调度问题的分派启发式算法[J]．系统工程理论与实践，1999，19(1)：27-33
[11]杨长春，顾永才.国际物流[M].北京：首都经济贸易大学出版社，2003
[12]朱新民.物流运输管理[M].大连：东北财经大学出版社，2004

11