【10校赛论文】送货路线设计问题

《【10校赛论文】送货路线设计问题》由会员分享，可在线阅读，更多相关《【10校赛论文】送货路线设计问题（35页珍藏版）》请在金锄头文库上搜索。

1、1送货路线设计问题送货路线设计问题1.1. 问题重述问题重述现今社会网络越来越普及，网购已成为一种常见的消费方式，随之物流行 业也渐渐兴盛。当顾客在网上订购货物之后，网店方面的工作人员（送货员） 需要以最快的速度及时将货物送达到顾客处，而且他们往往一人送多个地方， 于是便需要一个合理的送货方案使得送货员在规定时间内将货物送到，而且设 计方案应使其耗时最少。现有一快递公司，库房在城市的 O 点，一送货员需将货物送至城市内多处， 请设计送货方案，使所用时间最少。假定送货员只能沿题目所给连通线路行走， 而不能走其它任何路线。假定送货员最大载重 50 公斤，所带货物最大体积 1 立方米。送货员的平均

2、速度为 24 公里/小时。假定每件货物交接花费 3 分钟，为简化起见，同一地点 有多件货物也简单按照每件 3 分钟交接计算。现在送货员要将 100 件货物送到同一城市的 50 个地点。根据上述所述，请 完成以下问题： 1. 若将 130 号货物送到指定地点并返回。设计最快完成路线与方式。给 出 结果。要求标出送货线路。 2. 假定该送货员从早上 8 点上班开始送货，要将 130 号货物的送达时间 不能超过指定时间，请设计最快完成路线与方式。要求标出送货线路。 3. 若不需要考虑所有货物送达时间限制(包括前 30 件货物)，现在要将 100件货物全部送到指定地点并返回。设计最快完成路线与方式。要

3、求标出 送货线路，给出送完所有快件的时间。由于受重量和体积限制，送货员 可中途返回取货。可不考虑中午休息时间。注意：城市地形图示意图见附录一，各件货物的相关信息见附录二，50 个 位置点的坐标见附录三，各点连通信息见附录四。2.2. 模型假设模型假设1) 假设送货员最大载重 50 公斤，所带货物最大体积 1 立方米。 2) 假设送货员只能沿题目所给连通线路行走，而不能走其它任何路线。 3) 假设送货员在路上的平均速度恒为 24 公里/小时，即不考虑路途中出现的意 外情况。 4) 假设每件货物交接需花费 3 分钟，且为简化起见，同一地点有多件货物也简 单按照每件 3 分钟交接计算。 5) 假设该

4、送货员从早上 8 点上班开始工作送货，且不考虑中午休息时间。23.3. 问题分析问题分析该送货员须将网购货物送至应送地点，但根据实际情况送货员只能沿题目 所给连通线路行走，而不能走其它任何路线。为了尽量的节省时间，需要在满 足送货员送货不大于最大载重量、最大载物体积且根据题目要求在指定时间之 前完成任务的条件下，安排合适优化的送货路程，使路程最小即缩短送货时间， 使物流公司利益最大化。 对于问题一，根据题目要求可不考虑指定时间的限制，通过计算货物总重 量及货物总体积确定此题暂不用考虑送货重量及体积限制，通过计算任意两点 之间的最短路确定包含需送达地点的完备图，设置初始哈密顿圈并根据 TSP 近

5、 似算法对结果进行优化，找出最优即最短送货路径。 对于问题二，在问题一的基础上每点都必须考虑时间限制，同样不用考虑 送货重量及体积限制，于是可以在问题一算法的基础上加上限制条件，注意分 析同一时间限制条件下的点的位置分布特点，从而找出符合要求的最短路径。 对于问题三，按照题目限制，不考虑时间限制，但是有送货员配送的货物 的重量和体积的限制。综合总的重量和体积，结合送货员的限制条件，将所有 地点分成三组配送。然后我们根据求解第一问过程中生成的完备图生成了从 0 点到任一点的最短路图完成了分组工作，再进行优化配置使得总权（时间或路 程）最小。4. 符号说明符号说明5. 模型的建立与求解模型的建立与

6、求解5.1 问题一35.1.1 模型分析问题一要求将 130 号货物送到指定地点并返回，并不需要考虑指定时间的限制。对 130 号货物进行重量求和得到=48.5 公斤，=0.88 立方米。301M301V根据模型假设，送货员最大载重 50 公斤，所带货物最大体积 1 立方米，所以在 此题中不需要考虑货物重量及货物体积的限制，即送货员可从仓库 O 点将 130 号货物全部一次运送，中途不必再返回仓库取货物。因为送货员送货途中平均 速度恒定，且每件货物所需交接时间相同，不随送货点的变化而变化，所以本 题不必考虑送货点的先后、同一送货点货物的多少对送货时间的影响。 经过上述分析可得本题对结果可以产生

7、影响的因素只有送货路径的长短， 即送货路径最短，送货所需时间也便最少。因此此问题即最佳推销员回路问题。5.1.2 模型建立及求解送货问题也是 NP 完备问题。用顶点表示所有送货地点，边上的全表示距 离，于是送货问题就成为在加权图中寻找一条经过每个顶点至少一次的最短闭 通路问题。 依据以下定理： 定理定理 1：在加权图 G=(V,E)中，若对任意 x,y,zV,zx，zy,都有 w(x,y) w(x,z)+w(z,y),则图 G 的最佳 H 圈也是最佳推销员回路。 最佳推销员回路问题可转化为最佳 H 圈问题。方法是由给定图 G=(V,E)，构 造一个以 V 为顶点集的完备图 G=(V,E),E的

8、每条边（x，y）的权等于顶点 x 与 y 在途中最短路的权。 定理定理 2：加权图 G 的最佳推销员回路的权与 G的最佳 H 圈的权相同。 因此，在加权图中寻找最佳推销员回路的问题就可转化为在一个完备加权 图中寻求最佳哈密顿圈的问题，称为 TSP 问题。首先根据题目所给位置点的坐标信息（详见附录三） 、相互到达信息（详见 附录四） ，算出可连通两点间的实际距离（详见附录四） ，将所有点及连通距离 输入至图论软件，根据图论软件生成仓库点及送货点的具体信息可视图（如图 5-1-1 所示） 。4图 5-1-1、所有送货点加权图在图 5-1-1 中求最佳推销员回路问题是 NP-完备问题，常用解决最优化

9、路径 问题、NP-完全问题的方法有：模拟退火法、神经网络法、遗传算法、蚁群算 法等。但由于这些算法过于复杂，较难实现，故本文采用一种近似算法对模型 及问题进行求解。运用 TSP 近似算法中的一种改进型算法二边逐次修正法 求出该问题的一个近似最优解，来代替最优解。所谓改进型算法是以某一解作 为初始解，逐步迭代并改进解，最终找出最优解。根据图论软件及所输入的数据得出每两点间的最短路距离及路径，运用图 论软件画出这些点的最小生成树图（如图 5-1-2 所示） 。5图 5-1-2、货物点最小生成树图由于本文采用二边逐次修正法求解近似最优解，所以需要在 130 号货物所 在货物点中找出初始哈密顿圈。可以

10、根据货物运送地点的完备图来寻找初始哈 密顿圈。根据各货物号信息表（详见附录二）将 130 号货物所在货物点找出 （包含仓库 0 点共有 22 个点） ，根据之前产生的每两点间的最短路距离并运用 图论软件得出所找出货物送达点的完备图（详见附录五） 。 二边逐次修正法基本算法如下：（1） 、任取初始哈密顿圈：=， 。 （2） 、对所有的 i，j，1X(L(p+1)D=inf %如果某点到达时间超过限制条件，则令D为无穷大，相当于排除该路径breakendend%循环20000次，找出满足时间限制条件且D值最小的哈密顿圈，即为近似最优路径，其中任意两点的路径均为两点间的最短路径LMIN及其总长度DM

11、INif k=1DMIN=D;LMIN=L;elseif DDMINDMIN=D;LMIN=L;endendend LMINDMIN附录六附录六1、130 号货物送达点完备图权矩阵0.00,8455.64,11063.32,8916.34,3113.46,7092.43,10690.86,5714.34,6 687.55,6284.91,5217.16,12002.73,7541.90,8488.83,10026.24,8064.83, 9172.69,13562.36,12644.69,11671.28,15533.74,5295.49; 8455.64,0.00,2607.68,2195.

12、72,5342.18,3296.73,3970.24,8805.65,5488.4 7,8093.25,7025.50,5282.11,9350.25,6176.91,7714.33,9873.18,10981.0 3,11250.45,10332.77,9359.37,13221.82,5093.68; 11063.32,2607.68,0.00,3872.16,7949.86,5696.07,2097.64,11204.98,78 87.81,9674.57,9424.83,3409.51,11749.58,7470.65,5933.24,11454.49,1303380.36,9469.

13、36,8551.68,10653.11,11440.73,7493.01; 8916.34,2195.72,3872.16,0.00,5802.88,1823.91,1774.51,7332.82,4015.6 5,6620.43,5552.68,3086.38,7877.42,4704.09,5610.11,8400.35,9508.21,9 146.23,8228.55,7886.54,11117.60,3620.85; 3113.46,5342.18,7949.86,5802.88,0.00,3978.97,7577.40,3883.84,3574.0 9,3171.45,2103.69

14、,8889.26,4428.44,5375.36,6912.78,4951.37,6059.22,1 0448.90,9531.23,8557.82,12420.28,2182.03; 7092.43,3296.73,5696.07,1823.91,3978.97,0.00,3598.42,5508.91,2191.7 4,4796.52,3728.77,4910.29,6053.51,2880.18,4417.59,6576.44,7684.30,7 953.71,7036.04,6062.63,9925.09,1796.94; 10690.86,3970.24,2097.64,1774.5

15、1,7577.40,3598.42,0.00,9107.34,579 0.16,7576.93,7327.19,1311.87,9651.94,5373.01,3835.60,9356.85,1128 2.72,7371.71,6454.04,8555.47,9343.09,5395.37; 5714.34,8805.65,11204.98,7332.82,3883.84,5508.91,9107.34,0.00,331 7.17,2847.90,1780.15,9112.96,4104.89,5051.82,6589.24,4627.82,5735.6 8,10125.35,9207.68,

16、8234.27,12096.73,4709.23; 6687.55,5488.47,7887.81,4015.65,3574.09,2191.74,5790.16,3317.17,0.0 0,2604.78,1537.03,7102.03,3861.77,4808.70,6346.11,4384.70,5492.56,9 882.23,8964.56,7991.15,11853.61,1392.06; 6284.91,8093.25,9674.57,6620.43,3171.45,4796.52,7576.93,2847.90,2 604.78,0.00,1067.75,6265.06,3392.50,2203.92,3741.33,1779.92,5023. 28,7277.45,6359.78,5386.37,9248.83,3996.84; 5217.16,7025.50,9424.83,5552.68,2103