运输课程设计

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

2、复式行驶路线 23.2环形式行驶路线 23.3汇集式行驶路线 24车辆行驶路线的选择和优化 34.1环形式行驶路线的选择 3环形式行驶路线的优选标准 3 错误！未定义书签。4.2汇集式行驶路线的启发式算法 3 错误！未定义书签。 错误！未定义书签。 错误！未定义书签。5结论及设计体会 8参考文献 81车辆路径问题1.1车辆路径问题的产生背景美国物流管理学会（Council of Logistics Managemen, CLM）对物流所作的定义为：“为符合顾客的需要，对原料、制造过程中的存货与制成品以及相关信息，从其起运点 至最终消费点之间，做出的追求效率与成本效果的计划、执行与控制过程。”

3、而有关资料显示，物流配送过程（包含仓储、分拣、运输等）的成本构成中，运输成本占到 52% 之多。因此，如何在满足客户适当满意度的前提下，将配送的运输成本合理地降低，成 为一个紧迫而重要的研究课题，车辆路径问题正是基于这一需求而产生的。1.2车辆路径问题的定义车辆路径问题可以描述为：给定一组有容量限制的车辆的集合、一个物流中心（或 供货地）、若干有供货需求的客户，组织适当的行车路线，使车辆有序地通过所有的客 户，在满足一定的约束条件（如需求量、服务时间限制、车辆容量限制、行驶里程限制 等）下，达到一定的目标（如路程最短、费用极小、时间尽量少、使用车辆数尽量少等）。因此研究车辆路径问题，就是要研究

4、如何安排运输车辆的行驶路线，使运输车辆依 照最短的行驶路线或最短的时间费用，依次服务于每个客户后返回起点，总的运输成本 实现最小。2车辆行驶路线的类型2.1往复式行驶路线往复式行驶路线，是指运输过程中车辆在某一运输路线的两个端点之间做多次（包 括一次）往复行驶的路线类型。它又可以分成三种形式：单程有载往复式、回程部分有 载往复式和双程有载往复式。2.2环形式行驶路线环形式行驶路线是指车辆在由若干个装卸作业点组成的一条封闭回路上，作连续单向运行的行驶路线。由于各货运点在运输方向上的相互位置不同，这种形式的路线分为 三种形式，即简单环式、交叉或三角环式以及复合环式。2.3汇集式行驶路线汇集式行驶路

5、线是指车辆沿着分布于运行路线上各装卸作业点，依次完成相应的装卸作业，且每运次的货物装（卸）量均小于该车额定载质量，直到整个车辆装满（或卸 空）后返回出发点的行驶路线。般情况下，汇集式路线为封闭路线。车辆可能沿着一条 环形式的路线行驶，也可能在一条直线形路线上往返行驶。汇集式的运输形式一般可分为三种形式：（1）分送式：车辆从起点装车完成后，沿 着运行路线上的各个货运点依次进行卸货，最终可返回起点；（2）收集式：车辆从起点空车出发，沿着运行路线上的各个货运点进行装货，最终达到目的地；（3）分送一一收集式：车辆沿着运行路线上的各个货运点分别或者同时进行装货以及卸货。当车辆采用汇集式行驶路线完成运输任

6、务时，每次周转的货物周转量的大小与车辆 沿路线上各货运点的绕行次序有关。若绕行次序不同，即使完成同样货运任务其周转量 也不一样。在这种情况下，按总行程最短组织车辆进行运输最为经济。3车辆行驶路线的选择和优化3.1环形式行驶路线的选择环形式行驶路线的优选标准选择环形式行驶路线的原则是：当完成同样货运任务时，里程利用率B最高为最佳。环形式行驶路线以运次为基本运输过程进行组织，并且在一条环形路线上包含有多 个运次、多项货运任务。其中，每个运次的重车路线由货运任务决定，所以重车方向是 一定的，无从选择。那么，只有合理组织该环形路线各个运次的衔接顺序，使总空车行 程最短，才能使里程利用率B最高，才能获得

7、最经济的行驶路线。假设m为空车发点数（包括卸货点和车场），n为空车收点数（包括装货点和车场）， Q为由第i点发往第j点的空车数，q为第j点所需空车数，Q为第i点发出空车数，Lj为 第i点到第j点的距离，贝U其空车行驶路线的选择问题的数学模型如下： 目标函数是以全部车辆的总空车里程 Lv最短为求解目标，即约束条件：-=Q（i=1,2.(i=1,2,m)匸 1 =q (j=1,2,n)J=1 Q =03.2汇集式行驶路线的启发式算法汇集式行驶路线的优选原则是以每周转的总行程最短为最优。可将此问题归为运筹学中的货郎担问题，应用启发式算法来进行近似求解，其基本 思路是：当货运点多，总运量较大、需用运输

8、车辆超过一辆时，选择汇集式行驶路线首 先根据运输车辆每车次最高装载量定额，按就近调车的原则对货运点进行分组；然后按 总行程最短的原则，采用启发式算法分别确定每车沿其本组货运点的绕行次序，以选定 单车运行路线。首先确定计算所需数据，其中包括：货运点的分布图或货运点间里程矩阵 Lj ；货运 点收（卸）货量（q）;单车最高装载量（qH）。其中，i、j为货运点序号，q、qH的 计算单位视货物情况而定，如可以是吨、件、桶、箱、瓶等。A :确定货运点分组数d : d=工q/qH+0.5 B :单车货运点分组：其程序为：1） 确定单车行驶路线序号 N（ N=1, 2，d），即单车货运点分组组别序列，以依 次

9、确定单车行驶路线。2）选择第一个收货点。以K表示收货点的序号，即选择 K=1的收货点。首先确定距发货点（j=0 ）最远的收货点（j = r ）为第一个收货点，即确定 maxLj及车 辆实际载质量q=q ,并将该点记为2 = Ni,即第N组单车行驶路线上的第一个收货点。 此时第j收货点已收到所需数量（q）的货物，不再参加后续单车行驶路线上收货点的 分组选择，再令i=j ，继续选择下一个收货点。3） 选择其余收货点。即按照就近选点的原则，选取距上一个收货点（i=j=r ）最近 的第j （j）收货点为第K+1个收货点，此时车辆实际载质量增加至 q=q+q ;将该 点记为2 （k=k+1）。如果qv

10、6,则表明车辆载质量没有充分利用，若尚有 q工0，则继续选择本组下 一个收货点；如果q=5，表明本组单行驶路线上的全部货运点已选择完毕，转本程序第（1）步骤，进行第N+1组单车货运点的选择；如果qqH，表示车辆实际装载量已超过 车辆的每车次的最高装载定额，不能再负担第K+1个收货点的送货任务所以本组单车行 驶路线的全部收货点为K个，并按选点的先后顺序初排货运点序列 2,然后转本程序步 骤（1）进行下一组货运点的选择。若全部货运点的q=0,则表明本方案（S）的全部收货点选择完毕，据此，初排本组货运序列。若还有其它货运点分组方案，则转本程序第（1）步继续选择下一组别N+1的货运点，直至S=e方案分

11、组完毕，则转下一程序 C。C :选择单车货运点绕行次序。1）列出本组各货运点间里程（Lh）统计表，如表4-1所示。表内各点按初排货运点 顺序排列，包括收、发货点。表4-17NNNN.012mNd00Lo,1Lo,2Lo,mN1L1,o0L1,2Lo,m2L2,0L2,10L2,m2mLm,0Lm,1Lm,202）按M序列，选取前两个货运点（假定其序号分别为a、b）与发货点（j =0 ）组成初选循环回路，记为0ab0。按Nk序列，选取前两个货运点，组成初选循环回路。3）按2序列，依次选取货运点X插入初选循环回路。其插入原则是：回路中因包 含了货运点X（X）而使行驶路线长度的增加值（ ih）最小为

12、最优。即 ih=Li,x+L 1），则就要重复上述各步，选定该方案单 车绕行次序，直到全部方案（S=e）的单车货运点的绕行次序都确定为止。最后，从所有方案中选择总绕行里程最短（即 S : XLn =min ）的方案。某牛奶厂，拟采用一辆中型载重车（q=10吨）将鲜奶配送给6个固定的牛奶销售点， 要求采用启发式法选择车辆绕行次序，目标是在完成任务的前提下，绕行的总里程最短。表4-2各点之间的里程表BeBB3B5B6B00811107912B10956108B206469B30476B401210B5011B60表4- 3各牛奶销售点的需求表销售点B1B2B3B5Bs需求(吨)435222解：(1

13、)程序A：计算货运点的分组数d,即d=艺 qj/q h+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,检查

14、车辆是否达到满载，此时车辆装载的货物为2+5+2=9吨，还差一吨就会满载，但是其他的送货点所需求的送货量都超过了1吨，所以第一辆车的装载完成，运输路线也已经确定，接下来只需要选择此车的下一次绕行路线就可以了。 重复第二步的做法，选出此车的下一次运输路线，首先排除已经选择好了的点，选择 距离B0最远的点B2,此时B2距离B0最远，为11,并检查车辆装载率，此时车辆装载 的货物为3吨，未达到满载，所以这辆车可以继续装载货物。 选择第二辆车的第二个送货点，距离B2最近的B5,距离为6,检查车辆装载率，此时车辆装载的货物为3+2=5吨，未达到满载，可以继续装载货物。 第二辆车最后一个送货点为 B1,此

15、是车辆装载的货物为3+2+4=9吨，车辆运输安排完 毕。得出货运点分组方案如表4-4表4-4货运点分组方案统计表方 S组别N初排货运点序列jI16，3，422，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

16、-5-1-0 ih =9；因为行驶路线增加值最小为6,所以应选择循环回路0-1-2-5-0 此时单车绕行里程为32.结果如表4-5表4-5方 S组别N单车绕行路线单车绕行里程绕行里程合计I10-6-3-4-0296120-1-2-5-032由于此题只有方案I一种方案，所以此方案即为本题的最佳单车绕行路线方案，单车绕 行里程合计为61。4结论及设计体会在物流快速发展的大背景下，正确合理地安排车辆的运行线路，实现合理的线路运 输，可以有效地节约运输时间，增加车辆利用率，从而降低运输成本，提高企业经济效 益与客户服务水平，使企业达到科学化的物流管理，这也是企业提高自身竞争力的有效 途径之一。通过此次课程设计，我明白了车辆运行线路的优化对物流的重要性，不仅知道了 车辆行驶线路的类型，更是学习到并掌握了一些运行线路的优化方法，总之，这次课程 设计让我受益匪浅。参考文献1 胡思继.交通运输学M.北京：人民交通出版社，2001.2 陈京.汽车运输组织管理M.北京：机械工业出版社，20043 王之泰.现代物流学M.北京：中国物资出版社，20014 杨兆升.智能运输系统概论M.北京：人民交通出版社，2003孙媛.企业物流网络规划研究.同济大学学位论文，20086 李静.基于道路网络影响的物流运输成本