文档介绍：基于深度优先搜索算法的快递派送策略研究     市场周刊·理论研究③因MTSP问题求解难度较大,所以把MTSP问题转化为TSP解决,以求解最短路程。   (二)   MTSP问题转化为TSP问题来求解n个顶点,m个旅行商的MTSP问题可以转化为n'=n+m-1个顶点的TSP问题求解。   扩大的   (m-1)个顶点称为“人造顶点”,其距离矩阵W=[Wi,j]n×n转化为矩阵W'=[W'i,j]n'×n',设原问题矩阵为:扩大顶点以后的距离矩阵为:所以转化后的TSP模型如下:目标函数:约束条件:注解:约束条件①保证每个派送点只能去送货一次,停留一次;   约束条件②保证每个派送点只能离开一次;   约束条件③有解,则得到的任何圈一定包含原点,并且圈是可行的;   约束条件④为0-1变量约束;   约束条件   ⑤为非负约束。   (三)基于最小生成树的深度优先搜索法寻找运行路线1、根据TSP模型所得的结果,将它分为d1,d2,…,di满足d1<d2<…<di且d1+d2+…+di为所求的最短路径,d1,d2,…,di分别代表每组所走路程的上限,令d1,d2,…,di为初值,再设S1,S2,…,Si为实际每组的路程;   2、选择最小生成树中任一点为起点,将该点与原点的最短路程赋值给S1进行深度优先搜索,S1=S1+(树上连续搜索两点之间的最短距离),若S1+(正在搜索点到原点的最短距离)>d1,则停止搜索;   3、在以上所找点中找到一条与原点相连且距离在d1限制范围内的一条至少过顶点一次的回路;   4、   找到这条回路中所包括点(除原点外)中最后搜索的点,将此点作为寻找回路2的起点;   5、将d   1改为d2,…,di重复(2)~(4);   6、找出i条回路后,如此时d   1+d2+…+di已比所求的最短路程大或d1,d2,…,di不满足限制条件退出,否则以步长5改变d1,d2,…,di重复以上步骤。   根据上面的方法求得合理的运行路线即可。   二   、实例分析某快递公司,假定所有快件在早上7点钟到达,早上9点钟开始派送,要求与当天17点之前必须派送完毕,每个业务员每天平均工作时间不超过6小时,在每个送货点停留的时间为10分钟,途中速度为25km/h,每次出发最多能带25千克的重量。   为了计算方便,将快件一律用重量来衡量,,公司总部位于坐标原点,每个送货点的位置和快件重量如表1所示,并且假设街道平行于坐标轴方向。为该公司提供一个合理的派送策略(需要多少业务员,每个业务员的运行线路,以及总的运行公里数)。   表1送货点的位置及快件重量   点的分布如下:图1送货点的位置分布首先对问题作如下假设:1、公司总部每次发货的对象是无差别的;   2、尽量满足每条路线负重总量均衡;   3、业务员行走拐弯的时间,路上的意外事故的耽搁时间忽略;   4、   街道平行于坐标轴方向。   显然这是一个多旅行商问题,可将其转化为单旅行商问题,而对于TSP(单旅行商)问题可以利用LINGO软件来求解,解得最短总路程为492公里。   根据上文提到的深度优先搜索法得到合理的运行路线,并计算每条路线的公里数和运行时间,结果如表2所示:ááèéèééèéèééèéèéèéèéèéè