Abstract: To harmonize the relationship between logistics and reverse logistics and to describe the characteristics of vehicle with variable speed more specifically in urban logistics,a model of Time Dependent Vehicle Routing Problem with Simultaneous Delivery and Pickup (TDVRPSDP) was built.Aiming at reducing the costs of logistics activity,a Hyper-Heuristic (HH) algorithm was designed to solve TDVRPSDP.The proposed algorithm utilized Tabu Search (TS) as select strategy and Simulated Annealing (SA) as acceptance criteria (AC) in high-level heuristic to improve the performance of hyper-heuristic framework by timely and rapidly monitoring the performance information of Low-Level Heuristics (LLH) and choosing the best one according to its performance before.Simulation results and comparisons showed that the proposed algorithm was effective to solve TDVRPSDP within reasonable computing time.In addition,the ability to jump out local optimum and speed up optimizing of strategies designed had been proved by the test of benchmark instance and comparison of result from predecessor.

Key words: vehicle routing problem, simultaneous delivery and pickup, time dependent network, hyper-heuristics algorithm, tabu search

摘要： 为有效地协调正逆向物流,更好地体现城市物流配送速度时变的特点,降低物流配送成本,以时间依赖型同时取送货车辆路径问题为对象,建立其数学规划模型;设计了基于禁忌搜索的超启发式算法对其进行求解。在算法高层,设计了基于禁忌搜索评分制的选择策略及模拟退火的接收准则,实时监控底层启发式算子的性能并选择最优算子。通过基准实例测试及实验对比分析,表明了该算法能快速地找到满意解,所设计高层策略能保证算法跳出局部最优并快速收敛,从而证明了所提算法求解该问题的有效性。

关键词: 车辆路径问题, 同时取送货, 时间依赖网络, 超启发式算法, 禁忌搜索