摘要
对时变网络车辆调度问题提出一种满足先入先出准则的时变处理方法,并建立相应的数学模型,提出一种基于大规模邻域搜索技术的智能优化算法进行求解,算法顶层采用动态规划算法搜索环状交换邻域以得到每辆车的最佳服务顾客集合;底层设计动态搜索算法用以安排每辆车的最佳服务路线.在此基础上提出顶层加入虚拟顾客和底层嵌入insert两类改进策略.通过实验仿真比较,验证了所提算法的有效性.
Time dependent vehicle routing problem was formulated by dealing with time periods crossing with first-in first-out property, and a novel intelligent optimization algorithm based on very large scale neighborhood search technology was developed to solve it. In the upper level dynamic programming algorithm was adopted to search cycle transfer neighborhood so as to obtain the optimal customer set for each vehicle, while in the lower level dynasearch heuristics was developed to rank the customers in each vehicle. Based on this, two improvements were given： adding dummy customer in the upper level and embedding insert in the lower level. The efficiency of the method are testified with the results of extensive computational tests.
出处
《管理科学学报》
CSSCI
北大核心
2012年第1期22-32,共11页
Journal of Management Sciences in China
基金
国家自然科学基金资助项目(71001005)
中国博士后科学基金资助项目(20090460196)
中国博士后特别资助项目(201003043)
中央高校基本科研业务费专项资金资助项目(SWJTU11CX087)
四川省教育厅社会科学研究项目(09SB066)
关键词
时变网络车辆调度问题
先入先出
大规模邻域搜索
动态搜索算法
time dependent vehicle routing problem
first-in first-out
very large scale neighborhood search
dynasearch algorithm
