基于深度优先搜索算法的快递派送策略研究

1、基于深度优先搜索算法的快递派送策略研究     市场周刊·理论研究因 MTSP 问题求解难度较大，所以把 MTSP 问题转化为TSP 解决，以求解最短路程。    （二）    MTSP问题转化为TSP问题来求解n个顶点，m个旅行商的MTSP问题可以转化为n'=n+m- 1个顶点的TSP问题求解。    扩大的    (m- 1)个顶点称为“人造顶点”，其距离矩阵W=Wi，jn×n转化为矩阵W

2、9;=W'i，jn'×n'，设原问题矩阵为：扩大顶点以后的距离矩阵为：所以转化后的 TSP 模型如下：目标函数：约束条件：注解：约束条件保证每个派送点只能去送货一次，停留一次；    约束条件保证每个派送点只能离开一次；    约束条件有解，则得到的任何圈一定包含原点，并且圈是可行的；    约束条件为 0- 1 变量约束；    约束条件    为非负约束。    （三）基于最小生

3、成树的深度优先搜索法寻找运行路线1、根据 TSP 模型所得的结果，将它分为 d1,d2，di满足d1d2di且 d1+d2+di为所求的最短路径，d1，d2，di分别代表每组所走路程的上限，令 d1，d2，di为初值，再设 S1，S2，Si为实际每组的路程；    2、选择最小生成树中任一点为起点，将该点与原点的最短路程赋值给S1进行深度优先搜索，S1=S1+ (树上连续搜索两点之间的最短距离)，若 S1+(正在搜索点到原点的最短距离) >d1，则停止搜索；    3、在以上所找点中找到一条与原点相连且距离在 d1限制范围内的一

4、条至少过顶点一次的回路；    4、    找到这条回路中所包括点（除原点外）中最后搜索的点，将此点作为寻找回路2的起点；    5、将 d    1改为d2，di 重复（2）（4）；    6、找出 i 条回路后，如此时 d    1+d2+di已比所求的最短路程大或d1，d2，di不满足限制条件退出，否则以步长5改变d1，d2，di重复以上步骤。    根据上面的方法求得合理的运行路

5、线即可。    二    、实例分析某快递公司，假定所有快件在早上7点钟到达，早上9点钟开始派送，要求与当天17点之前必须派送完毕，每个业务员每天平均工作时间不超过6小时，在每个送货点停留的时间为10分钟，途中速度为25km/h，每次出发最多能带25千克的重量。    为了计算方便，将快件一律用重量来衡量，平均每天收到总重量为 184.5 千克，公司总部位于坐标原点，每个送货点的位置和快件重量如表 1 所示，并且假设街道平行于坐标轴方向。为该公司提供一个合理的派送策略（需要多少业务员，每个业务员的运行线路

6、，以及总的运行公里数）。    表1送货点的位置及快件重量    点的分布如下：图1送货点的位置分布首先对问题作如下假设：1、公司总部每次发货的对象是无差别的；    2、尽量满足每条路线负重总量均衡；    3、业务员行走拐弯的时间，路上的意外事故的耽搁时间忽略；    4、    街道平行于坐标轴方向。    显然这是一个多旅行商问题，可将其转化为单旅行商问题，而对于TSP（单旅行商

7、）问题可以利用 LINGO 软件来求解，解得最短总路程为 492 公里。    根据上文提到的深度优先搜索法得到合理的运行路线，并计算每条路线的公里数和运行时间，结果如表2 所示：á á èé è é éè é èé éèé è é è éèé è éè è è è è è é

8、èé éè é è è éè è è é éè è á èá è5 10 15 20 25x5101520y- 22-2012 年第 1 期前言随着物流业的发展，快递行业应运而生，同时网购的普及更是为快递公司带来丰厚的利润。快递公司在不断谋取利润的同时，也为我们的生活带来许多方便。就目前我国快递公司的营运状况来说，一般地，当所有快件到达某地后，会集中存放在总部，然后由业务员分别进行派送。对于快递公司，为了保

9、证快件能够在指定的时间内送达目的地，必须要雇佣足够的业务员进行送货，同时还要选择合适路径以节省送货时间。因此，确定业务员数量和优化送货路径是快递公司不得不面临的抉择，显然，这属于典型的 TSP 问题。    TSP 问题是一个具有广泛应用背景和重要理论价值的组合优化难题，但问题本身在概念上却很简单：有 N 个城市，一个旅行商从某个城市出发，遍历所有城市后回到出发点，求一条经过所有城市仅一次的最短遍历路径。其形式化描述为：给定一个连通图G=（V，E，W），其中 V 为顶点集合，E 为边的集合，W 为边的非负权值集合，经过连通图所有顶点恰好一次的回路称为Hamilto

10、n 回路，记为 T，WT为 Hamilton 回路所有边权值的和，求WT 最小的 Hamilton 回路。对 N 个顶点的连通图 G，其不同的Hamilton 回路数为（N- 1）！/2。城市管道铺设优化、物流等行业中的车辆调度优化、制造业中的切割路径优化等现实生活中的优化问题都可以归结为 TSP 来求解。在计算机算法理论中，TSP 已经被证明是一个 NP- Hard 问题，即找不到一种算法能在多项式时间内求得问题的最优解。    这意味着随着问题规模的增大，很难在较短的时间内求得问题的精确值，只能找到“亚优解”（SubOptimal Solution）。

11、0;   一    、送货策略算法选择在公司确定快递派送策略时，通常认为快件是无差别的，但每次业务员的承受重量是有限的，即送货过程中存在载重限制。    另外鉴于快递行业的特殊性质，业务员每天的工作时间也是有限制的。合理的快递派送策略需在满足每次送货的载重限制和工作时间限制的基础上，使得业务员运行的总路程最短，以此作为目标函数确定需要的业务员的数目以及送货路线。    由于顾客多是散点状分布，这里涉及分组离散的网络图论问题。在确定派送策略时，我们可以通过合理的假设，将其转化为 MTSP

12、 问题，因 MTSP 问题求解难度较大，可把 MTSP 问题转化为 TSP 问题解决，即可求出总的最短送货路程。以此最短路程为限制条件，利用基于最小生成树的深度优先搜索算法寻找合适的运行路线，并结合实际情况中的载重限制，对找出的运行路线进行调整修正，即可得出符合要求的运行路线。    下面利用 TSP 的相关理论对问题进行分析。    （一）MTSP 问题原理    给定 n 个城市（V1，V2Vn），m 名旅行商皆以城市 V0为基地。令 Wi，j表示 Vi城到 Vj城的距离。 ，指一条巡回路线。 为巡回

13、 的总路程。目标是选择m 条巡回路线使总路程最小，目标函数如下：当 Wij=Wji时，称为对称型 MTSP。    目标函数：以总的运行公里数最短为目标约束条件：最短路径的约束注解： ，为 0- 1 变量；    不存在子巡回路；    丁 洁    （上海海事大学科学研究院，上海 200135）基于深度优先搜索算法的快递派送策略研究摘 要：随着经济的快速发展，尤其是网购的盛行，快递行业呈现出日益蓬勃的发展态势。本文针对快递公司送货策略的选择这一典型的 TSP 问题，充分考虑

14、各个路线的送货量以及业务员工作时间的均衡，以所有业务员经过的总路程最短为目标函数建立数学模型。而后以得出的结论为基础，利用基于最小生成树的深度优先搜索算法，最终找到符合要求的“亚优解”派送策略。      关键词：    TSP 问题；最小生成树；最优路径；送货策略      中图分类号：    F259.22 文献标识码：B 文章编号：1008- 4428（2012）01 03管理探索- 21-2012 年第 1 期（上接第67 页）参考文献： 

15、;   1杨临春.    我国商业银行的信用风险管理    J.    当代财经    ,2006.    2张鹏.商业银行信用风险度量与控制J. 财经理论与实践,2008.    3    陈平.我国商业银行信用风险内部评级体系研究D.北京物资学院,2007.    4    李德志,郝云宏. &

16、#160;  中国国有商业银行效率分析    J.    当代经济科学    ,2005,(01).    5    杨晓.    我国商业银行个人理财业务的问题及建议J.    现代商业    ,2007,(12).    作者简介：    章家清，男，浙江宁波人，日本明治大学博士（经济

17、），现为江南大学商学院副教授；    张兆鑫，男，黑龙江哈尔滨人，江南大学商学院硕士（经济）。    表    2 每条路线的运行情况根据每个快递员允许所带重量限定修正上面的结果，题目中要求的运行时间及重量限制分别为：原则1：每个业务员工作时间不超过 6 小时，送货点停留的时间为10 分钟；    原则    2：每次出发最多能带 25 千克的重量；    原则    3：考虑每条路线载

18、重量和每个业务员工作时间的均衡。    利用上面的三个原则，对表    2 进行修正，同时组合每个业务员的送货时间，所得结果如表 3 所示：表3每条路线的运行情况由表 3 知，根据工作时间均衡的原则，分别将路线 2 和路线8 合并，路线 6 和路线 7 合并，合并后每条路线由一个业务员送货，因此只需要6 个业务员。最终调整后的每个业务员的运行路线如表 3 和图 2 所示，业务员的总运行路程为 546 公里。    图2每条路线的运行情况    本算法在对题目全面理解和把握的基

19、础上，根据要求，对快递派送方案的优化模型采用逼近搜索的方法，得到近似解。由于派送过程中有负重的约束条件，使得每个业务员的工作时间较短，多在4个小时左右，相较于题目中每个业务员最长工作时间6小时，表面上看利用率不足。    考虑到现实中快递公司多会聘用    兼职人员以及混合型员工（部分时间送货，部分时间做其他工作），因此本文得出的结论很有现实意义。    三    、结束语本文针对快递派送策略的选择问题，由于目前解决多旅行商问题的直接方法仍不够完善，故先将多旅行商问题巧妙地转

20、化为单旅行商问题，利用其成熟的理论进行求解。根据时间限制条件，结合最小生成树的深度优先搜索算法确定业务员的运行路线，得到近似最优解，求解的精度和时间效率都比较高。基于目前快递行业的发展态势，该算法的得出很有现实意义。另外也可将其应用到其他方面的问题研究之中，如灾情巡查路线、垃圾处理问题等。    参考文献：    1 薛毅，耿美英. 运筹学与实验 M. 北京：电子工业出版社，2008.    2 阮怀忠，张建中. 基于改进遗传算法的 TSP 问题求解J. 安徽建筑工业学院学报（自然科学版），2003,11

21、（4）：53- 56.    3 姜昌华，胡幼华.一种求解旅行商问题的高效混合遗传算法J.    计算机工程与应用，2004,(22):67- 70.    4    萧树铁，姜启源，高立等. 大学数学第二版数学实验M. 北京：高等教育出版社，2005.    5 刘育兴，钟剑. 垃圾运输问题的模型及其求解J. 赣南师范学院学报，2006，7（3）：52- 55.    6 耿素云，屈婉玲. 离散数学M. 修订版.

22、北京：高等教育出版社，2004.    7    谢金星，薛毅. 优化模型与 LINDO/LINGO 软件M. 北京：清华大学出版社，2005.    8 贺一，刘光远. 紧急搜索算法求解旅行商问题研究J. 西南师范大学学报（自然科学版），2002，27（7）：341- 345.    9 毕守东，胡焱等. 最佳巡视路线模型研究J. 安徽农业大学学报，2000，27（2）：178- 181.    作者简介：    丁洁，女，山东临沂人，上海海事大学科学研究院硕士研究生，研究方向：技术经济评价与决策。 &