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

送货路线设计问题1.问题重述现今社会网络越来越普及，网购已成为一种常见的消费方式，随之物流行业也渐渐兴盛。当顾客在网上订购货物之后，网店方面的工作人员（送货员）需要以最快的速度及时将货物送达到顾客处，而且他们往往一人送多个地方，于是便需要一个合理的送货方案使得送货员在规定时间内将货物送到，而且设计方案应使其耗时最少。现有一快递公司，库房在城市的O点，一送货员需将货物送至城市内多处，请设计送货方案，使所用时间最少。假定送货员只能沿题目所给连通线路行走，而不能走其它任何路线。假定送货员最大载重50公斤，所带货物最大体积1立方米。送货员的平均速度为24公里/小时。假定每件货物交接花费3分钟，为简化起见，同一地点有多件货物也简单按照每件3分钟交接计算。现在送货员要将100件货物送到同一城市的50个地点。根据上述所述，请完成以下问题：1.若将1~30号货物送到指定地点并返回。设计最快完成路线与方式。给出结果。要求标出送货线路。2.假定该送货员从早上8点上班开始送货，要将1~30号货物的送达时间不能超过指定时间，请设计最快完成路线与方式。要求标出送货线路。3.若不需要考虑所有货物送达时间限制(包括前30件货物)，现在要将100件货物全部送到指定地点并返回。设计最快完成路线与方式。要求标出送货线路，给出送完所有快件的时间。由于受重量和体积限制，送货员可中途返回取货。可不考虑中午休息时间。注意：城市地形图示意图见附录一，各件货物的相关信息见附录二，50个位置点的坐标见附录三，各点连通信息见附录四。2.模型假设1)假设送货员最大载重50公斤，所带货物最大体积1立方米。2)假设送货员只能沿题目所给连通线路行走，而不能走其它任何路线。3)假设送货员在路上的平均速度恒为24公里/小时，即不考虑路途中出现的意外情况。4)假设每件货物交接需花费3分钟，且为简化起见，同一地点有多件货物也简单按照每件3分钟交接计算。5)假设该送货员从早上8点上班开始工作送货，且不考虑中午休息时间。3.问题分析35 该送货员须将网购货物送至应送地点，但根据实际情况送货员只能沿题目所给连通线路行走，而不能走其它任何路线。为了尽量的节省时间，需要在满足送货员送货不大于最大载重量、最大载物体积且根据题目要求在指定时间之前完成任务的条件下，安排合适优化的送货路程，使路程最小即缩短送货时间，使物流公司利益最大化。对于问题一，根据题目要求可不考虑指定时间的限制，通过计算货物总重量及货物总体积确定此题暂不用考虑送货重量及体积限制，通过计算任意两点之间的最短路确定包含需送达地点的完备图，设置初始哈密顿圈并根据TSP近似算法对结果进行优化，找出最优即最短送货路径。对于问题二，在问题一的基础上每点都必须考虑时间限制，同样不用考虑送货重量及体积限制，于是可以在问题一算法的基础上加上限制条件，注意分析同一时间限制条件下的点的位置分布特点，从而找出符合要求的最短路径。对于问题三，按照题目限制，不考虑时间限制，但是有送货员配送的货物的重量和体积的限制。综合总的重量和体积，结合送货员的限制条件，将所有地点分成三组配送。然后我们根据求解第一问过程中生成的完备图生成了从0点到任一点的最短路图完成了分组工作，再进行优化配置使得总权（时间或路程）最小。1.符号说明2.模型的建立与求解5.1问题一5.1.1模型分析35 问题一要求将1~30号货物送到指定地点并返回，并不需要考虑指定时间的限制。对1~30号货物进行重量求和得到=48.5公斤，=0.88立方米。根据模型假设，送货员最大载重50公斤，所带货物最大体积1立方米，所以在此题中不需要考虑货物重量及货物体积的限制，即送货员可从仓库O点将1~30号货物全部一次运送，中途不必再返回仓库取货物。因为送货员送货途中平均速度恒定，且每件货物所需交接时间相同，不随送货点的变化而变化，所以本题不必考虑送货点的先后、同一送货点货物的多少对送货时间的影响。经过上述分析可得本题对结果可以产生影响的因素只有送货路径的长短，即送货路径最短，送货所需时间也便最少。因此此问题即最佳推销员回路问题。5.1.2模型建立及求解送货问题也是NP完备问题。用顶点表示所有送货地点，边上的全表示距离，于是送货问题就成为在加权图中寻找一条经过每个顶点至少一次的最短闭通路问题。依据以下定理：定理1：在加权图G=(V,E)中，若对任意x,y,z∈V,z≠x，z≠y,都有w(x,y)≤w(x,z)+w(z,y),则图G的最佳H圈也是最佳推销员回路。最佳推销员回路问题可转化为最佳H圈问题。方法是由给定图G=(V,E)，构造一个以V为顶点集的完备图G’=(V,E’),E’的每条边（x，y）的权等于顶点x与y在途中最短路的权。定理2：加权图G的最佳推销员回路的权与G’的最佳H圈的权相同。因此，在加权图中寻找最佳推销员回路的问题就可转化为在一个完备加权图中寻求最佳哈密顿圈的问题，称为TSP问题。首先根据题目所给位置点的坐标信息（详见附录三）、相互到达信息（详见附录四），算出可连通两点间的实际距离（详见附录四），将所有点及连通距离输入至图论软件，根据图论软件生成仓库点及送货点的具体信息可视图（如图5-1-1所示）。35 图5-1-1、所有送货点加权图在图5-1-1中求最佳推销员回路问题是NP-完备问题，常用解决最优化路径问题、NP-完全问题的方法有：模拟退火法、神经网络法、遗传算法、蚁群算法等。但由于这些算法过于复杂，较难实现，故本文采用一种近似算法对模型及问题进行求解。运用TSP近似算法中的一种改进型算法——二边逐次修正法求出该问题的一个近似最优解，来代替最优解。所谓改进型算法是以某一解作为初始解，逐步迭代并改进解，最终找出最优解。根据图论软件及所输入的数据得出每两点间的最短路距离及路径，运用图论软件画出这些点的最小生成树图（如图5-1-2所示）。35 图5-1-2、货物点最小生成树图由于本文采用二边逐次修正法求解近似最优解，所以需要在1~30号货物所在货物点中找出初始哈密顿圈。可以根据货物运送地点的完备图来寻找初始哈密顿圈。根据各货物号信息表（详见附录二）将1~30号货物所在货物点找出（包含仓库0点共有22个点），根据之前产生的每两点间的最短路距离并运用图论软件得出所找出货物送达点的完备图（详见附录五）。二边逐次修正法基本算法如下：（1）、任取初始哈密顿圈：=，，…，…，…，，。（2）、对所有的i，j，1X(L(p+1))D=inf%如果某点到达时间超过限制条件，则令D为无穷大，相当于排除该路径breakendend%循环20000次，找出满足时间限制条件且D值最小的哈密顿圈，即为近似最优路径，其中任意两点的路径均为两点间的最短路径LMIN及其总长度DMINifk==1DMIN=D;LMIN=L;else35 ifD