资源描述：
《数模送货路线论文》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。
1、一、问题重述现今社会网络越来越普及，网购已成为一•种常见的消费方式，随之物流行业也渐渐兴盛，每个送货员需要以最快的速度及时将货物送达，而且他们往往一人送多个地方，请设计方案使其耗时最少。现冇一快递公司，库房在图I屮的0点，一送货员需将货物送至城市内多处,请设计送货方案，使所用时间最少。该地形图的示意图见图1,各点连通信息见表3。各件货物的相关信息见表1,50个位置点的坐标见表2。现在送货员要将100件货物送到50个地点。问题如K问题一：若将1〜30号货物送到指定地点并返冋。设计最快完成路线与方式。给出结果。要求标出送货线路。问题二
2、：假定该送货员从早上8点上班开始送货，要将1〜30号货物的送达吋间不能超过指定时间，请设计最快完成路线与方式。要求标出送货线路。问题三：若不需要考虑所冇货物送达时间限制（包括前30件货物），现在耍将100件货物全部送到指定地点并返冋。设计最快完成路线与方式。要求标出送货线路，给出送完所有快件的时间。由于受重量和体积限制，送货员可屮途返冋取货。可不考虑中午休息时间。图一二、基本假设1、假设送货员的最大载重是50公斤，所带货物的最大体积为1立方米；2、假设送货员的路上平均速度为24公里/小时，不会出现意外现象；3、每件货物交接花费3分
3、钟，同一地点有多件货物也简单按照每件3分钟交接计算，不会岀现特殊情况而延误时间；4、送货员只沿示意图连线路径行走；5、假设快递公司地点0为第51个位置点；6、假设送货员回到出发点0后取货时间不计。三.符号定义及说明D两点最短路径距离矩阵Vi(1,2,...n)从1到50个位置点里n个位置点集合/(V,)从0/51点出发，经过匕中所有点最后回到0/51点的最佳送货路线的权值（即总路程）T送货员完成一次送货的时间HVi集合所有位置点要送达的货物件数问题的分析快递公司的送货员需要把货物送到所冇货物交接地点，最后回到出发点。问如何安排送货
4、路线，能最快完成任务，即总的送货行程最短。此即图论中最佳推销员路径问题。若不考虑送货员最大载重和体积，两个位置点边上的权表示距离，于是问题就成为在加权图屮寻找一条经过每个位置点至少一次的最短闭通路问题，即求最佳哈密尔顿圈（H圈），也即是NP■完备问题。用矩阵翻转方法來实现二边逐次修止法过程，求最佳哈密尔顿圈（H圈）。五、模型的建立与求解准备工作：用MATLAB编程先求出附表给定的相互之间可直接到达地点之间的距离:序号位置点1位置点2距离（米）113191621828643220782342422935381958634353675
5、1550058521253961129410718591811714510128121757139142681149101946810/51182182820/51211797830/51261392用上表各地点的距离可构造示意图的带权邻接矩阵，再用Floyd算法求每对地点Z间最短路径。1.Floyd算法的基木思想直接在示意图的带权邻接矩阵中用插入顶点的方法依次构造出n个矩阵D⑴、D⑵、…、DV,使最后得到的矩阵成为图的距离矩阵,同时也求出插入点矩阵以便得到两点间的最短路径.用Matlab编程得D(51)=(DQ51X51,其中D
6、(i,j)即为两点最短路径距离，1234567849500/5110774519165452899812941968286420306169891006827745058292293125390399713778725570220011629631916582903536708232103884195820705173881046745452229335360354667467420549424241209241400358998125370823546010292109669040243172074816563612949039
7、32106746102920326241582160018283113627196897133884742010966326204832183381502181008286477871958549490404158483201874715430850949203062557020705242412431721600183381874703569117215016989220011738820924207481828315021154303569099280/5110068162961046714003165631136281008
8、5091172199280基本概念令G=(V,E)为一个加权无向图，其中V二丨vl,v2,……,vn
9、为顶点集合，E为边集合。图G中每一条边e都对应一个实数w（e）,则称w（e）为该边的权。若任意两点均有边相连，则G为完备图。哈密尔顿图设G二（V,
