[1]夏红云,江亿平,赵林度.基于双层规划的应急救援车辆调度模型[J].东南大学学报(自然科学版),2014,44(2):425-429.[doi:10.3969/j.issn.1001-0505.2014.02.035]
 Xia Hongyun,Jiang Yiping,Zhao Lindu.Emergency rescue vehicle scheduling model based on bi-level programming[J].Journal of Southeast University (Natural Science Edition),2014,44(2):425-429.[doi:10.3969/j.issn.1001-0505.2014.02.035]
点击复制

基于双层规划的应急救援车辆调度模型()
分享到:

《东南大学学报(自然科学版)》[ISSN:1001-0505/CN:32-1178/N]

卷:
44
期数:
2014年第2期
页码:
425-429
栏目:
经济与管理
出版日期:
2014-03-20

文章信息/Info

Title:
Emergency rescue vehicle scheduling model based on bi-level programming
作者:
夏红云江亿平赵林度
东南大学系统工程研究所, 南京 210096
Author(s):
Xia Hongyun Jiang Yiping Zhao Lindu
Institute of Systems Engineering, Southeast University, Nanjing 210096, China
关键词:
多阶段 时间窗 应急车辆调度 双层规划
Keywords:
multi-period time window emergency vehicle scheduling bi-level programming
分类号:
C94
DOI:
10.3969/j.issn.1001-0505.2014.02.035
摘要:
为了在有限时间域内最大化各灾区应急资源需求满足量、减少延迟成本,采用网络流理论及双层规划建模方法,构建了含时间窗的应急救援车辆多次、多阶段动态调度模型,并利用基于动态规划的两阶段启发式算法进行求解.算例结果表明,最优解形成了集覆盖调度方案,即从供应点1出发的车辆覆盖需求点(1,3,7,8),从供应点2出发的车辆覆盖需求点(2,4,6),从供应点3出发的车辆覆盖需求点(1,5).在最优调度方案下,总延迟成本为0.双层规划能降低求解维度,上下层合作关系保证了全局最优的实现.因此,应急管理部门应先行决策应急资源的战略配置以有效提高各阶段救援车辆调度效率.
Abstract:
To maximize the total satisfied demand of disaster areas and minimize the cost of delay within a limited time domain, a multi-time and multi-period model of emergency vehicle dynamic scheduling with time windows is constructed by using the network flow theory and bi-level programming modeling method. And a two-phase heuristic algorithm based on dynamic programming is put forward to solve this problem. The numerical results indicate that the optimal solution is a set-cover scheduling scheme. The vehicles from supply point 1 cover demand points(1,3,7,8); the vehicles from supply point 2 cover demand points(2,4,6); the vehicles from supply point 3 cover demand points(1,5). The total cost of delay is 0 under the optimal solution. The bi-level programming can degrade the dimension of the solution, and the cooperation relationship between the upper level and the lower level guarantees the realization of global optimization. Therefore, the emergency management department should first make strategic decisions of emergency resource allocation to effectively enhance the efficiency of the vehicle scheduling during each period.

参考文献/References:

[1] Dantzing G, Ramser J. The truck dispatching problem[J]. Management Science, 1959, 6(1): 80-91.
[2] Brandão J. A tabu search algorithm for the heterogeneous fixed fleet vehicle routing problem[J]. Computers & Operations Research, 2011, 38(1): 140-151.
[3] Belfiore P C, Yoshizaki H T Y. Scatter search for a real-life heterogeneous fleet vehicle routing problem with time windows and split deliveries in Brazil[J]. European Journal of Operational Research, 2009, 199(3): 750-758.
[4] Bettinelli A, Ceselli A, Righini G. A branch-and-cut-and-price algorithm for the multi-depot heterogeneous vehicle routing problem with time windows[J]. Transportation Research Part C: Emerging Technologies, 2011, 19(5): 723-740.
[5] Azi N, Gendreau M, Potvin J. An exact algorithm for a single-vehicle routing problem with time windows and multiple routes[J]. European Journal of Operational Research, 2007, 178(3): 755-766.
[6] Xu L Y. A heuristic algorithm for the multi-period vehicle routing problem with simultaneous pickup and delivery service[D]. Hong Kong: Hong Kong University of Science and Technology, 2010.
[7] Wen M, Cordeau J, Laporte G, et al. The dynamic multi-period vehicle routing problem[J]. Computers & Operations Research, 2010, 37(1): 1615-1623.
[8] Yuan Y,Wang D W. Path selection model and algorithm for emergency logistics management[J]. Computers & Industrial Engineering, 2009, 56(3): 1081-1094.
[9] Wohlgemuth S, Oloruntoba R, Clausen U. Dynamic vehicle routing with anticipation in disaster relief[J]. Socio-Economic Planning Sciences, 2012, 46(4): 261-271.
[10] 石彪,池宏,祁明亮, 等. 应急物资运输的两阶段车辆调度模型[J]. 系统工程,2012, 30(7): 105-111.
  Shi Biao, Chi Hong, Qi Mingliang, et al. A two-stage vehicle scheduling model of transportation of emergency resources [J]. Systems Engineering, 2012, 30(7): 105-111.(in Chinese)

相似文献/References:

[1]陈美军,张志胜,史金飞.基于自适应多态蚁群算法的多约束车辆路径问题[J].东南大学学报(自然科学版),2008,38(1):37.[doi:10.3969/j.issn.1001-0505.2008.01.008]
 Chen Meijun,Zhang Zhisheng,Shi Jinfei.Vehicle routing problem with multiple constraints using adaptive and polymorphic ant colony algorithm[J].Journal of Southeast University (Natural Science Edition),2008,38(2):37.[doi:10.3969/j.issn.1001-0505.2008.01.008]

备注/Memo

备注/Memo:
收稿日期: 2013-08-19.
作者简介: 夏红云(1988—),女,硕士生; 赵林度(联系人), 男,博士,教授,博士生导师,ldzhao@seu.edu.cn.
基金项目: 国家自然科学基金资助项目(70671021).
引用本文: 夏红云,江亿平,赵林度.基于双层规划的应急救援车辆调度模型[J].东南大学学报:自然科学版,2014,44(2):425-429. [doi:10.3969/j.issn.1001-0505.2014.02.035]
更新日期/Last Update: 2014-03-20