送货线路设计问题数学建模

《送货线路设计问题数学建模》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、数学建模论文送货路线设计问题xxxxxx20年7月7日21摘要针对本题要解决的问题，由于它不是一个完全的欧拉回路，但它可以转化为在遍历所有要送达货物节点的前提下，使总路程最小。用Floyd算法迭代出任意两点最短路的距离矩阵，并将原来的图构造成完全图。问题一：将1~30号货物送到指定地点并返回，构造最优Hamilton回路，设计出最快完成路线与方式，给出结果为总路程是：W=53787.24m；最优时间是：T=3.7411h。问题二：基于问题一，在添加了时间限制的情况下，即在满足时间条件约束时求最短路径的问题，从而转化多区域最短路模型，设计最

2、佳方案，给出结果为总路程：W=5499.64m；总时间为：T=11.7911h。问题三：由于考虑到送货员一次送货所能承载的最大重量和体积，要达到送货时间最短，从而转化为多阶段最短路模型，设计最佳方案，给出结果。关键字：Floyd算法多区域最短路多阶段最短路问题欧拉回路Hamilton回路21一、问题重述现今社会网络越来越普及，网购已成为一种常见的消费方式，随之物流行业也渐渐兴盛，每个送货员需要以最快的速度及时将货物送达，而且他们往往一人送多个地方，请设计方案使其耗时最少。现有一快递公司，库房在图1中的O点，一送货员需将货物送至城市内多处，

3、请设计送货方案，使所用时间最少。该地形图的示意图见图1，各点连通信息见表3，假定送货员只能沿这些连通线路行走，而不能走其它任何路线。各件货物的相关信息见表1，50个位置点的坐标见表2。假定送货员最大载重50公斤，所带货物最大体积1立方米。送货员的平均速度为24公里/小时。假定每件货物交接花费3分钟，为简化起见，同一地点有多件货物也简单按照每件3分钟交接计算。现在送货员要将100件货物送到50个地点。请完成以下问题。1.若将1~30号货物送到指定地点并返回。设计最快完成路线与方式。给出结果。要求标出送货线路。2.假定该送货员从早上8点上班开

4、始送货，要将1~30号货物的送达时间不能超过指定时间，请设计最快完成路线与方式。要求标出送货线路。3.若不需要考虑所有货物送达时间限制(包括前30件货物)，现在要将100件货物全部送到指定地点并返回。设计最快完成路线与方式。要求标出送货线路，给出送完所有快件的时间。由于受重量和体积限制，送货员可中途返回取货。可不考虑中午休息时间。二、模型假设1．假设送货员的最大载重是50公斤，所带货物的最大体积为1立方米；2．假设送货员回到出发点O后取货时间不计；3．每件货物交接花费3分钟，同一地点有多件货物也简单按照没见3分钟交接计算；4．对于某些至少

5、要经过两次以上的送货点，认为仅在第一次经过是停留，即每第一次经过时就把所有货物一次性送到；5．要求到达的时间不包括此次在该点交易的时间；6．所用的精确数据都精确到0.01m，时间精确到0.0001h；7．在满足时间限制的条件下，顾客能够更早的拿到货物，顾客的满意度越高；8．送货员在多次经过同一送货地点时，在第一次经过就交接货物效率最高。三、符号说明符号符号说明送货点的标号从O点回到O点的最短回路距离21从O点回到O点所用的总时间从送货点到送货点的最短距离送货员的平均速度从O点到的最短时间到达可以带的最多货物质量到达可以带的最大的货物体积一

6、次可以携带的最多货物的总质量一次可以携带的最多货物的总体积四、问题分析送货路线问题可以理解为：已知起点和终点的图的遍历问题的合理优化的路线设计。图的遍历问题的指标：路程和到达的时间，货物的质量和体积，以及最大可以负载的质量和体积。在路线的安排问题中，考虑所走的路程的最短即为最合理的优化指标。对于问题一1~30号货物的总重量是48.5公斤，总体积是0.88立方米，均在送货员的最大承受范围，所以不用考虑送货员返回取货。由于送货地点确定，在每个送货地点交界的时间均为3分钟，因此总的交接时间确定，只需要求解最优路线问题。若不考虑送货员最大载重和体

7、积，两个位置点边上的权表示距离，于是问题就成为在加权图中寻找一条经过每个位置点至少一次的最短闭通路问题，即求最佳哈密尔顿圈。对于问题二则要考虑每件货物送达时间的要求，而每件货物对应相应的送货地点，从而转化为到达指定送货地点的时间限制，而时间的限制可以分为几个时间段，因此采用以时间为基础的多区域最短路的假设模型从而找出最优解。对于问题三要在体积和质量的双重限制下得到送货员最快完成送货的路线，1~100号货物的总重量是148公斤，总体积是2.8公斤，根据时间和体积的限制，送货员至少要往返三次送货，又由于每次不可能刚好带满50kg而如果只要三次

8、则最多只能带150kg只比原货物多2kg所以不可能是三次就把货物带完，最少要四次，所以将问题分为四个阶段进行求解。五、模型的建立与求解我们使用Flody算法求出两点间的最短路径，图采用邻接矩阵