运输课程设计--车辆行驶路线
山东交通学院《运输工程》课程设计
摘要
目前，现代物流产业已经是覆盖整个产业链的、全方位的、立体化的服务供应商， 国家和企业也越来越重视物流在国民经济中的重要地位。现代物流被看作是降低资源消 耗、提高人力素质之后的“第三利润源” 。在物流领域中，车辆行驶路线选择始终是 一个重要的组成部分, 特别是在最近几十年中，许多学者都对其进行了大量的实验和研 究。本文首先介绍了车辆路径问题的产生背景及定义，然后由此引出并介绍了车辆行驶 路线的类型，以及行驶路线的选择和优化方法，并针对汇集式行驶路线的启发式算法进 行了实例分析。
1.2 车辆路径问题的定义
车辆路径问题可以描述为：给定一组有容量限制的车辆的集合、一个物流中心（或 供货地）、若干有供货需求的客户，组织适当的行车路线，使车辆有序地通过所有的客 户，在满足一定的约束条件（如需求量、服务时间限制、车辆容量限制、行驶里程限制 等）下，达到一定的目标（如路程最短、费用极小、时间尽量少、使用车辆数尽量少等）。
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 个收货点的送货任务所以本组单车行
思路是：当货运点多，总运量较大、需用运输车辆超过一辆时，选择汇集式行驶路线首 先根据运输车辆每车次最高装载量定额，按就近调车的原则对货运点进行分组；然后按 总行程最短的原则，采用启发式算法分别确定每车沿其本组货运点的绕行次序，以选定 单车运行路线。 3.2.2启发式算法求解流程
首先确定计算所需数据，其中包括:货运点的分布图或货运点间里程矩阵 Lij；货运 点收（卸）货量（qj）； 单车最高装载量（qH）。 其中，i、j 为货运点序号，qj 、qH 的 计算单位视货物情况而定，如可以是吨、件、桶、箱、瓶等。
假设m为空车发点数（包括卸货点和车场），n为空车收点数（包括装货点和车场）， Qij为由第i点发往第j点的空车数，qj为第j点所需空车数，Qi为第i点发出空车数，Lij为 第i点到第j点的距离，则其空车行驶路线的选择问题的数学模型如下： 目标函数是以全部车辆的总空车里程LV最短为求解目标，即
minLV=
约束条件：
=Qi
=qj (j=1,2,…,n)
(i=1,2,…,m)
Qij >=0
6
山东交通学院《运输工程》课程设计
3.2 汇集式行驶路线的启发式算法
3.2.1启发式算法概述 汇集式行驶路线的优选原则是以每周转的总行程最短为最优。 可将此问题归为运筹学中的货郎担问题，应用启发式算法来进行近似求解，其基本
…
…
…
…
…
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
当车辆采用汇集式行驶路线完成运输任务时，每次周转的货物周转量的大小与车辆 沿路线上各货运点的绕行次序有关。若绕行次序不同，即使完成同样货运任务其周转量 也不一样。在这种情况下，按总行程最短组织车辆进行运输最为经济。
3 车辆行驶路线的选择和优化
3.1 环形式行驶路线的选择
3.1.1 环形式行驶路线的优选标准 选择环形式行驶路线的原则是：当完成同样货运任务时，里程利用率 β 最高为最
因此研究车辆路径问题，就是要研究如何安排运输车辆的行驶路线，使运输车辆依 照最短的行驶路线或最短的时间费用，依次服务于每个客户后返回起点，总的运输成本 实现最小。
2 车辆行驶路线的类型 2.1 往复式行驶路线
往复式行驶路线，是指运输过程中车辆在某一运输路线的两个端点之间做多次（包 括一次）往复行驶的路线类型。它又可以分成三种形式：单程有载往复式、回程部分有 载往复式和双程有载往复式。
5
山东交通学院《运输工程》课程设计
卸作业，且每运次的货物装（卸）量均小于该车额定载质量，直到整个车辆装满（或卸 空）后返回出发点的行驶路线。般情况下，汇集式路线为封闭路线。车辆可能沿着一条 环形式的路线行驶，也可能在一条直线形路线上往返行驶。
汇集式的运输形式一般可分为三种形式：（1）分送式：车辆从起点装车完成后，沿 着运行路线上的各个货运点依次进行卸货，最终可返回起点；（2）收集式：车辆从起点 空车出发，沿着运行路线上的各个货运点进行装货，最终达到目的地；（3）分送——收 集式：车辆沿着运行路线上的各个货运点分别或者同时进行装货以及卸货。
8
山东交通学院《运输工程》课程设计
最 后 ， 从 所 有 方 案 中 选 择 总 绕 行 里 程 最 短 （ 即 S ： ∑LN =min ）的方案。 3.2.3启发式算法实例分析
某牛奶厂，拟采用一辆中型载重车（q=10 吨）将鲜奶配送给 6 个固定的牛奶销售点， 要求采用启发式法选择车辆绕行次序，目标是在完成任务的前提下，绕行的总里程最短。
4) 计算本组货运点绕行里程 LN
LN= 5) 依次确定下一组（第 N+1 组）单车货运点的绕行次序，直到各组货运点绕行次 序全部确定完毕（N=d）。然后求本方案各组绕行里程合计∑LN。
6) 如果还有其它货运点分组方案（即 S＞1），则就要重复上述各步，选定该方案 单车绕行次序，直到全部方案(S=e)的单车货运点的绕行次序都确定为止。
①确定第一组的第一个送货点，即距离B0最远的送货点，根据各点之间的里程表可以确
定第一个点是B6,其距离B0为12，并检查车辆是否已经装满，此时车辆装载的货物为2
吨，车辆未达到满载.
3.1 往复式行驶路线 .......................................... 5 3.2 环形式行驶路线 .......................................... 5 3.3 汇集式行驶路线 .......................................... 5 4 车辆行驶路线的选择和优化 ......................................... 6 4.1 环形式行驶路线的选择 .................................... 6
2.2 环形式行驶路线
环形式行驶路线是指车辆在由若干个装卸作业点组成的一条封闭回路上，作连续单 向运行的行驶路线。由于各货运点在运输方向上的相互位置不同，这种形式的路线分为 三种形式，即简单环式、交叉或三角环式以及复合环式。
2.3 汇集式行驶路线
汇集式行驶路线是指车辆沿着分布于运行路线上各装卸作业点，依次完成相应的装
7
山东交通学院《运输工程》课程设计
驶路线的全部收货点为 K 个，并按选点的先后顺序初排货运点序列 NK，然后转本程序步 骤（1）进行下一组货运点的选择。若全部货运点的 qj=0，则表明本方案（S）的全部收 货点选择完毕，据此，初排本组货运序列。若还有其它货运点分组方案，则转本程序第 （1）步继续选择下一组别 N+1 的货运点，直至 S=e 方案分组完毕，则转下一程序 C。
佳。环形式行驶路线以运次为基本运输过程进行组织，并且在一条环形路线上包含有多 个运次、多项货运任务。其中，每个运次的重车路线由货运任务决定，所以重车方向是 一定的，无从选择。那么，只有合理组织该环形路线各个运次的衔接顺序，使总空车行 程最短，才能使里程利用率β最高，才能获得最经济的行驶路线。 3.1.2 数学模型
4.1.1 环形式行驶路线的优选标准 ....................... 6 4.1.2 数学模型 ....................................... 6 4.2 汇集式行驶路线的启发式算法 .............................. 7
3
山东交通学院《运输工程》课程设计
表 4-2 各点之间的里程表
Bj
B0
B1
B2
B3Байду номын сангаас
B4
B5
B6
Bi
B0
0
8
11
10
7
9
12
B1
0
9
5
6
10
8
B2
0
6
4
6
9
B3