动态车辆路径问题的分区灵活分批TSP策略
熊 浩
海南大学经济与管理学院，海口570228
Email：xh_xionghao@126.com
摘 要：动态车辆路径问题是当前车辆路径问题的新兴热门问题。但是，其实时优化策略研究仍然有较大的改进空间。为此，在一般分区分批TSP策略的基础上，提出了分区灵活分批TSP策略，并对策略有效性进行了分析。最后，对该策略进行了实例仿真验证，结果表明该策略的确能减少车辆服务顾客的平均行驶距离，从而减少顾客的平均系统时间。
关键词：动态车辆路径问题；实时优化策略；有效性分析；仿真分析
中图分类号：N945 文献标识码：
A flexible nTSP strategy of dynamic vehicle routing problems
Xiong Hao
(1. School of Economics and Management, Hainan University, Haikou 570228, China. Email：xh_xionghao@126.com)
Abstract:Dynamic Vehicle Routing Problem (DVRP) is emerging topical issues for the vehicle routing problem, but its real-time optimization still needs to be improved. Therefore, the flexible nTSP strategy is proposed, which is based on the flexible nTSP strategy. And the competitive analysis of the new strategy shows the reason of the improvement. The new strategy can reduce the average distance between the adjacent customers on the routing of vehicle while keeping the other system time constant. So, the average customer system time can be reduced. Finally, the simulation of the strategy is given. And the result of the numerical example proved those conclusions.窗体底端
Key words: Dynamic vehicle routing problem; real-time optimization strategy; competitive analysis; simulation analysis
1引言
近年来，随着城市经济的发展和规模的不断扩大，各种各样动态的交通需求与日俱增。比如：集装箱货物的集散运输、批发市场的零担货运以及快递服务的末端集货和发货；生产商或销售商配送中心的按需补货或者紧急补货；汽车抢修或维修服务的修理员实时响应；出租车或电话叫车服务的车辆调度；警车、救火车、救护车等紧急服务的车辆调度等等。这些与日俱增的动态交通需求构成了日益突出的城市交通拥堵的主要原因之一，如何应对这些动态的交通需求、提高车辆出行的效率，成为迫切需要研究的重要课题。
动态车辆路径问题由Psaraftis在80年代末提出[1]。但90年代后期，动态车辆路径问题才逐渐得到一定程度的重视。目前，该类问题的实时优化策略可分为两类：算法为主的策略和规则为主的策略。
以算法为主的策略为了突出动态车辆路径问题的动态特性，往往以新顾客的出现作为决策的触发机制，每次新顾客到达就进行路径的优化。该类策略一般以算法研究为主，括三种类型：局部优化、全局优化和综合优化[2]，具体表现为：插入法[3, 4]、禁忌搜索[5, 6]、列生成法[7]、蚁群算法[8]、遗传算法[9]等。后来，Bent 等[10]针对短期目标与长期目标的矛盾性提出了适应能力强的多计划方法（Multiple Plan Approach MPA）和考虑预测信息的多场景方法（Multiple Scenario Approach MSA）。
以规则为主的策略比较重视规则对优化目标的影响，从而比较侧重对规则的研究。Bertsimas等较早并提出了基于排队论的一系列构建静态子问题的策略[11-13]，包括：先到先服务策略（FCFS）、随机中心排队策略（Stochastic Queue Median，SQM）、定量TSP策略（n-sized Traveling Salesman Problem strategy，nTSP）、分区定量TSP策略（the modified nTSP，mod nTSP）、分格策略（the Partition strategy，PART）、就近策略（the Nearest Neighbor，NN）和填充曲线策略（the Space Filling Curve，SFC）；后来，郭耀煌和钟小鹏也利用排队论构建了中点重定位策略[14]；郭耀煌、谢秉磊（2003）对一类需求密集情况下的随机动态车辆路径问题的期望系统时间下界以及TSP策略的渐近性能进行了分析[15]；Smith研究了多种需求到达率的情况下的排队策略[16]。还有一类研究比较侧重对等待地选择和再分配规则策略的研究，比如：原地等待和等候点等候的研究[17] [18] [19]；以及再分配规则的策略有GEN策略[20]和RH策略[21]。