配送线路计算及优化

配送线路计算及优化课程:《智能运输管理》一、配送车辆调度的含义配送车辆调度是指物流配送车辆调度问题是把一系列的装货点和（或）卸货点，有机的组织起来，形成一系列行车线路，使待调度车辆能够高效、节能且有序地通过这些点，最终达到缩短里程、减少开支费用、缩短运输时间、使用车辆数尽量少等优化目标。物流配送车辆调度是在配送中心及用户位置均已知、资源及运输能力充分、各用户需求量己知的前提下，如何合理、高效、低成本的解决分配与运送的问题，也就是说如何将货物从配送中心按照一定的要求发送到若干个用户点。二、配送车辆调度的构成要素车辆2客户4运输网络5约束条件6目标函数7物流中心3货物1二、配送车辆调度的构成要素01固定，即不随时间和车辆的不同而变化04既随时间不同而变化，又随车辆不同而变化02随时间不同而变化03随车辆的不同而变化运输网络运输网络是由顶点(指物流中心、客户、停车场)、无向边和有向弧组成的。边、弧的属性包括方向、权值和交通流量限制等。边或弧的权值变化的情况分为：二、配送车辆调度的构成要素无流量限制1边、弧限制，即每条边、弧上同时行驶的车辆数有限2顶点限制，即每个顶点上同时装、卸货的车辆数有限3边、弧、顶点都有限制4运输网络对运输网络中顶点、边或弧的交通流量要求分为以下几种情况：三、配送路线优化配送路线是指各送货车辆向各个用户送货时所要经过的线路。配送路线是否合理对配送速度、车辆的合理利用和配送费用都有直接影响，因此配送线路的优化问题是配送工作的主要问题之一。采用科学、合理的方法来确定配送路线，是配送活动中非常重要的一项工作。四、配送路线的确定原则01效益最高。这种目标是指以企业的利润值尽可能大为目标。选择以效益最高为目标主要考虑的是当前效益，同时也兼顾长远效益。由于效益是企业各项经济活动的综合反映，单纯与配送路线建立联系并不能客观真实反映对效益的确切影响，因此一般很少采用这一目标。020304成本最低。配送路线与配送成本之间有密切的关系，计算配送路线的送货成本相对效益目标而言相对简化，具有可操作性，是比较实用且常用的选择目标。路程最短吨公里最小05准时性最高06运力运用最合理07劳动消耗最低（一）确定目标四、配送路线的确定原则满足所有收货人对货物品种、规格以及数量的要求满足收货人对货物发到时间范围的要求在允许通行的时间内进行配送，各配送路线的货物量不得超过车辆容积和载重量的限制在已有送货运力资源允许的范围内。（二）确定配送路线的约束条件五、配送路线优化的方法根据送货作业的实际情况，送货业务中最多出现的是以下两种情况：从单个配送中心向单个客户往返送货及从单个配送中心向多个客户循环送货后返回。这两种情况的配送线路最短路线设计可以归结为两类问题，即两点间最短路问题和单起点多回路最短路线问题。五、配送路线优化的方法两点间最短路计算的方法始发点作为已解点，计算从始发点开始。第n次迭代的目标。寻求第n次最近始发点的节点,重复n＝1,2,…,直到最近的节点是终点为止。第n次迭代的输入值。(n-1)个最近始发点的节点是由以前的迭代根据离始发点最短路线和距离计算而得的。这些节点以及始发点称为己解的节点,其余的节点是尚未解的点。第n次最近节点的候选点。每个己解的节点由线路分支通向一个或多个尚未解的节点,这些未解的节点中有一个以最短路线分支连接的是候选点。第n个最近的节点的计算。将每个己解的节点及其候选点之间的距离和从始发点到该已解节点之间的距离加起来，总距离最短的候选点即是第n个最近的节点,也就是始发点到达该点最短距离的路径。六、节约里程法解决单起点多回路最短路线问题的方法最常用的方法是“节约里程法”，它是形成人工和计算机计算单起点多回路最短路线的基础。六、节约里程法（一）节约里程法的基本思想见下图：OABbacO点为配送中心所在地，A和B为客户所在地,三者相互间的道路距离分别为a、b、c。从配送中心O要运送货物给客户A和B。第一条路线是从O-A-O,然后再从O-B-O,总距离为a+a+b+b=2a+2b，还可以选择另外一种路线，从O-A-B-O。总距离为：a+b+c。结合客户综合考虑,在第二种方案下行驶路线的节约里程数是：(2a+2b)-(a+b+c)即：a+b-c

六、节约里程法（一）节约里程法的基本思想说明：3465因为三角形的两条边之和总是大于第三条的，因此，它从不为负，最小为零将客户连接起来，增加了节约；客户之间的距离越近，而且它们距离配送中心越远，那么节约就会越大；这个方法也可以用时间来代替距离计算六、节约里程法（二）节约里程法的使用条件01适用于有稳定客户群的配送中心02各配送线路的负荷要尽量均衡；0203要考虑客户要求的交货时间（即一条线路的送货总里程不能太长，否则会影响向客户交货时间的准确性还要考虑货物总量不能超过车辆的额定载重量。节约里程法实例某配送中心为其他地区的10个门店送货，因配送中心的送货资源有限，不能为每个门店单独送货，只能一辆车一趟为几个门店循环送货。配送中心的现有送货限制为：只有额定载重分别为2吨和4吨两种厢式货车可供送货（即送货路线上各客户的货物总重小于2吨的使用2吨的车型，超过2吨的用4吨的车型，但送货路线上各门店的货物总重最多不超过4吨）考虑到达门店装卸后交付时间、送货路上时间、综合成本等因素，每辆车每次送货的成本不能超过30。节约里程法实例配送初始方案图节约里程法实例O

A10A

B94B

C795C

D814105D

E8181496E

F8181715137F

G313121011116G

H4141311121282H

I10111517181817119IJ7481315151510118配送成本最低线路数值表解题步骤节约里程法计算（步骤一）第一步：根据“配送中心到各门店及两两门店之间成本最低线路的数值表（见上表）”和节约法的基本原理，计算出两两门店之间的节约成本。计算方法是：i,j是任意相邻两门店节点Oi=a，OJ=b，ij=c，则i—j节约的成本为：a+b-c。例如：A，B两点的节约成本为，OA+OB-AB＝10+9-4＝15。计算结果填入表中。

A

B15B

C811C

D4710D

E03310E

F00039F

G000015G

H0000045H

I94000125I

J1381000009J配送成本节约数值表解题步骤节约里程法计算（步骤二）第二步：根据上表中的出两两门店之间的节约成本计算结果，按节约成本大小顺序排列到表中。序号连接点节约里程序号连接点节约里程1A—B1513F—G52A—J1313G—H53B—C1113H—I54C—D1016A—D44D—E1016B—I46A—I916F—H46E—F919B—E36I—J919D—F39A—C821G—I29B—J822C—J111B—D722E—G112C—E622F—I1配送成本节约数值排序表解题步骤节约里程法计算（步骤三）第三步：有了以上计算数据后就可以对初始的送货路线进行优化了。左图是初始方案，从配送中心分别向各个门店节点送货，共有10条送货路线，总成本数为148，需载重2吨的货车10辆。解题步骤节约里程法计算（步骤四）第四步：按节约成本的大小顺序链接A-B,A-J,B-C,同时取消O—B、O-A路线,形成巡回路线,如下图所示。这时配送路线共有7条，各条线路总成本为109，需要载重2吨的货车6辆，4吨的货车1辆。见左图（图中绿色线条代表选中的线路，红色线条代表取消的线路，后续各图均同）。由图可知,规划的配送路线1，装载货物3.6吨，成本为27。解题步骤节约里程法计算（步骤五）第五步：按节约成本大小顺序,应该是C-D和D-E,C-D有可能并到二次解线路1中,但目前配送路线1已装载货物3.6吨运行成本为27公里，考虑到单车载重量和线路成本限制（每条线路成本不超过30）,配送路线1不能再增加送货门店,为此连接D-E,组成配送线路2,如左图所示。其装载重量为1.8吨,成本22。此时，共有配送线路6条，总成本99，需载重2吨的货车5辆，4吨的货车1辆。解题步骤节约里程法计算（步骤六）第六步：下面的节约成本大小顺序是A-I、E-F,由于门店A己组合到配送线路1中，该线路不再增加新门店，故不连接A-I;连接E-F并入配送线路2中，并取消O-E线路，此时配送线路共有5条,如左图所示。线路2的装载量为3.3吨,运行成本为29。此时，共有配送线路5条，总运行成本为90，需载重2吨的货车3辆,4吨的货车2辆。解题步骤节约里程法计算（步骤七）第七步：按节约成本顺序，接下来应该是I-J,A-C,B-J,B-D,C-E,但这些连接已包含在配送线路1或2中,不能再组合成新的线路。再下来是F-G,可组合在配送线路2中，如左图所示。此时，线路2的装载量为3.9吨,运行成本为30,这样共有4条线路,总成本为85,需载重2吨货车2辆,4吨的货车2辆。解题步骤节约里程法计算（步骤八）第八步：接下来的节约成本顺序为G-H,由于受装载量及线路里程的限制，不再组合到线路2中，故连接H-I组成配送线路3,其装载量为1.3吨,运行成本为23,此时，形成最终方案，如下图。共有三条配送线路，总成本为80,需