送货线路设计

送货线路设计问题摘要本文是关于快递公司送货路线设计问题，即在给定送货地点和给定设计规范的条件下，确定送货员的最短运行线路，即耗时最少的送货线路。

对于问题一，将1~30号货物送到指定地点并返回。

设计最快完成路线与方式，我们建立最短路径模型，用Dijkstra算法求算，还有图的遍历模型，即求最佳哈密尔顿圈。

在路线的安排问题中，考虑所走的路程的最短即为最合理的优化指标。

对于问题二，基于问题一，在添加了时间限制的情况下，即在满足时间条件约束时求最短路径的问题，从而转化多目标规划模型，分区域计算，设计最佳方案，标出最快完成路线。

对于问题三，包含两个方面：第一、对送货地点的分组；第二、在每组中求最佳送货路线。

由于考虑到送货员一次送货所能承载的最大重量和体积，要达到送货时间最短，通过一次送货的重量和体积的限制划分为三个区域，在每个区域中求出最优哈密尔顿回路，从而得到最短送完所有货物的线路图的满意解。

关键词：Dijkstra算法最佳哈密尔顿圈图的遍历模型分区域假设模型一：问题重述现今社会网络越来越普及，网购已成为一种常见的消费方式，随之物流行业也渐渐兴盛，每个送货员需要以最快的速度及时将货物送达，而且他们往往一人送多个地方，请设计方案使其耗时最少。

现有一快递公司，库房在图1中的O点，一送货员需将货物送至城市内多处，请设计送货方案，使所用时间最少。

该地形图的示意图见图1，各点连通信息见表3，假定送货员只能沿这些连通线路行走，而不能走其它任何路线。

各件货物的相关信息见表1，50个位置点的坐标见表2。

假定送货员最大载重50公斤，所带货物最大体积1立方米。

送货员的平均速度为24公里/小时。

假定每件货物交接花费3分钟，为简化起见，同一地点有多件货物也简单按照每件3分钟交接计算。

现在送货员要将100件货物送到50个地点。

请完成以下问题。

1. 若将1~30号货物送到指定地点并返回。

设计最快完成路线与方式。

给出结果。

要求标出送货线路。

2. 假定该送货员从早上8点上班开始送货，要将1~30号货物的送达时间不能超过指定时间，请设计最快完成路线与方式。

要求标出送货线路。

3. 若不需要考虑所有货物送达时间限制(包括前30件货物)，现在要将100件货物全部送到指定地点并返回。

设计最快完成路线与方式。

要求标出送货线路，给出送完所有快件的时间。

由于受重量和体积限制，送货员可中途返回取货。

可不考虑中午休息时间。

二：问题分析目前，快递行业正蓬勃发展，为我们的生活带来更多方便。

为了保证快件能够在指定的时间内和规范的条件下送达目的地，设计最快完成路线与方式成为了快递公司的首要之需。

快递公司不但要求每一件货物需要在指定的时间内送达，而且还要使每个送货员送货的路线最短，因此，如何用最少的时间准时完成所有的任务是最重要的。

（一）对问题一的分析：问题一要求得，在将1~30号货物送到指定地点并返回的前提下，建立一用时最省的送货员送货线路模型。

可以理解为：已知起点和终点的图的遍历问题的合理优化的路线设计。

图的遍历问题的指标：路程和到达的时间，货物的质量和体积，以及最大可以负载的质量和体积。

两个位置点边上的权表示距离，于是问题就成为在加权图中寻找一条经过每个位置点至少一次的最短闭通路问题，即求最佳哈密尔顿圈在路线的安排问题中，考虑所走的路程的最短即为最合理的优化指标。

（二）对问题二的分析：本问也是图上点的行遍性问题。

但由于此问题有时间限制因素在里面，也即较第一问多出了时间的限制条件，所以此问题可以归结为多目标规划问题。

要考虑到所到的点的时间的要求是否满足题意即采用多次分区域的假设模型从而找出最优的解统计可得:不超过九点的货物组成的集合为(18,13,24);不超过九点半的货物组成的集合为(31,34,40,45);不超过十点十五的货物组成的集合为(38,42,43,49 ）;不超过十二点的货物组成的集合为(14,16,17,21,23,26,32,36) 。

对这个多目标规划问题，考虑到不太容易转化为单目标问题求解，所以试用第一问的结论，如果满足，则就是最优解；如果不满足，这进行调试，求出满意解。

（三）对问题三的分析：要在体积和质量的双重限制下得到送货员最快完成送货的路线，1~100号货物的总重量是 148 公斤，总体积是 2.8 公斤，根据是时间和体积的限制，送货员至少要往返三次送货，又由于要求最快完成，则可通过在满足时间和体积的条件下划分区域求局部最短回路，从而得到全局最短路的满意解。

（三）模型假设（1）假设题目所给的数据真实可靠。

（2）到同一地点的货物要一次拿上，即不考虑再以后又经过时再带些货物。

（3）要求达到不超过的时间不包括此次在该点交易的时间。

（4）假设送货车辆不会在半路抛锚，半路无塞车现象，即送货员送快递途中不受任何外界因素影响，且无需考虑送货员的工作时间与休息时间。

（5）送货指定地点的大小，与送货线路长相比，它们相对地小得多，故可以抽象的看做一个点。

两指定送货地点之间的线路，省略其弯曲，抽象简化为直线段，而直线段的长即为此段线路的长度。

（四）定义与符号说明1.i,j 送货点的标号。

2.W 从o开始到回到o的总路程。

3.T 从o开始到回到o的总时间。

4.W（i，j）从i开始到j的最短路程。

5.V送货员的平均速度。

6.ti从o开始到i的最短时间。

7.mi到i可带的最大物品重量。

8.vi到i可带的最大的物品体积。

9.M一次可携带的最多物品的总质量。

10.V一次可携带的最多货物的总体积。

附：i，j=1、2、3……50 并且M=50kg V=1错误！未找到引用源。

（五）模型的建立与求解一．问题一的模型1、最短路径模型Dijkstra算法是图论中非常有名的一个算法。

我们为了求出各个点的之间的最短的路径，使用Dijstra算法求解。

（1）模型的建立图采用邻接矩阵的形式描述，w（i,j）表示结点i到结点j间的最短距离，如果没有直接连通，则为无穷大。

dijkstra算法只能求出从结点i到其它各结点的最短路径。

算法引入这样两个集合s和t，s是那些已经确定了到i结点的最短路径的结点，t为那些还未确定最短路径的结点。

s的初值是{i}，t的初值是u-{i}。

另外再引入一个标记数组d[n]，其中在某一步d[k]表示当前从i到k的较短路径，d[k]的初值为w（i，k）。

算法过程如下：１、在t中选择一个d[k]最小的结点k，将k并入s，并从t中去掉；２、用k结点和t中其余结点进行一遍比较，如果d[i]>d[k]+m[k][i]，则用d[k]+m[k][i]取代原来的d[i]，重复１；３、算法结束，此时d[k]中保存的就是从i到k结点的最短路径。

算法确定了从i到其余各结点的最短路径。

（2）模型的求解：根据算法和相邻的点的距离可以用dijkstra算法求出任意两点的最短路径。

使用循环的结构求出1-50各个点之间的最短距离。

程序可以求出w和tt为最短路径经过的点从o开始到其余50个点最短路程所经过得点是0 7 4 8 3 15 1 18 12 14 18 13 13 18 21 12 23 21 0 24 22 0 29 17 31 19 0 31 30 25 22 26 23 28 31 38 21 40 36 27 34 37 43 38 41 36 41 40 46 42 40如若从o到4点必须经过3点，经过3点必须经过8点经过8点必须经过12点经过12点必须经过13点，经过13点必须经过18点，18点与o点联通，所以从o到4点最短路径所经过的点是0-18-13-12-8-3-4。

2、图的遍历模型（1）模型的建立：共经过21个点，运送30件货物，两个位置点边上的权表示距离，于是问题就成为在加权图中寻找一条经过每个位置点至少一次的最短闭通路问题，即求最佳哈密尔顿圈（H 圈）。

该30件货物错误！未找到引用源。

=47.3kg<50kg 错误！未找到引用源。

=0.8371错误！未找到引用源。

,所以可以一次把货物携带进行运送。

前30件货物可以到达的地点：13、14、16、17、18、21、23、24、26、27、31、32、34、36、38、39、40、42、43、45、49。

且送货员不需要返回0 点重新取货，故只需要满足从0 点出发遍历图中的21 个点回到0 的距离最短即可。

目标函数是：T=W÷V+t0×30约束条件是：必须全部遍历回到0点本题要求出回到O点则可以看到两个开始最短遍历的点在某点重合即可完成最短的遍历。

（2）模型的求解：由程序得：最佳路径为即0 → 18 → 13 → 24 → 39 → 27 → 31 → 34 → 40 → 45 → 49 → 42 → 43 →38 → 36 → 32 → 23 → 16 → 14 → 17 → 21 → 26 → 0 。

总路程是：W=5.5555e+004m最优时间是：T= w/v+3/60*n=3.3648h二：问题二的模型分区域假设模型(1)模型的建立：由于问题一的解释无时间约束的最短路问题，因此，如果问题一的解满足问题二的时间要求，则问题一的解必为问题一的最优解。

尝试第一问的结论：0 → 18 → 13 → 24 → 39 → 27 → 31 → 34 → 40 → 45 → 49 → 42 → 43 →→ 38 → 36 → 32 → 23 → 16 → 14 → 17 → 21 → 26 → 0计算得:到达时间为Columns 1 through 178.1172 8.2969 8.5850 8.8278 8.9520 9.04659.1933 9.3113 9.4953 9.7232 9.8531 9.9413 10.100410.2145 10.4187 10.5234 10.6606Columns 18 through 2210.8193 10.9608 11.0868 11.2568 11.3648所以如果考虑实际误差不满足要求的点为：40 ，45 。

如下图所示的时间分区1,2,3,4 。

分析可得：1 区与2 区过渡点为(24,31) ；2 区与3 区过渡点为(45,42) ；3 区与4 区过渡点为(38,32) 。

由第一问行走路线可知：虽然 27 ， 31 点（ 4 区内）离 1 ， 2 区近可以考虑先走以缩短时间，但发现在问题一方法下（已是基本按时间区顺序行走）不满足时间限制。

同时由于 4 区点最多但分配的时间也最多，故可以考虑直接按时间顺序行走。

本题图形简单，易知路径为：0-18-13-24-31-34-40-45-49-42-43-38-32-23-16-14-17-21-36-39-27-26-0（2）模型求解：路径为：0-18-13-24-31-34-40-45-49-42-43-38-32-23-16-14-17-21-36-39-27-26-0根据程序计算得：w=5.4686e+004修正后到达时间为Columns 1 through 178.0909 8.2706 8.5587 8.6829 8.8298 8.94779.1318 9.3597 9.4895 9.5778 9.7369 9.8920 9.996710.1341 10.2928 10.4342 10.5602Columns 18 through 2210.7219 10.9379 11.0621 11.2206 11.3286认为此解为满意解三、问题三的模型（1）模型的建立：由附录给定的各货物号信息表，1~100号货物总重量148公斤、总体积2.8立方米。