基于特殊路径的局内车辆路径问题混合策略研究

运筹与管理 ›› 2011, Vol. 20 ›› Issue (5): 57-62.

基于特殊路径的局内车辆路径问题混合策略研究

马卫民, 董丹丹, 王珂

同济大学经济与管理学院,上海 200092

收稿日期:2010-04-03 出版日期:2011-10-25
作者简介:马卫民(1971-),男,陕西合阳人,教授,博士生导师,研究方向:运筹与运作管理,不确定决策理论与方法等; 董丹丹(1985-),女,河南平顶山人,硕士研究生,研究方向:不确定决策理论与方法; 王珂(1982-),男,重庆人,博士研究生,研究方向:决策分析与决策智能,物流与供应链管理。
基金资助:
国家自然科学基金项目(70671004,71071113);全国优秀博士论文作者专项科研资金资助(200782);高等学校博士学科点专项科研基金(20100072110011);上海市教育委员会曙光计划基金(08SG21);上海市浦江人才计划基金,上海市哲学社会科学规划课题(2010BZH003)。

Mixed Strategies for the Online Vehicle Routing Problem on a Special Road

MA Wei-min, DONG Dan-Dan, WANG Ke

School of Economics and Management, Tongji University, Shanghai 200092, China

Received:2010-04-03 Online:2011-10-25

摘要/Abstract

摘要： 针对运输途中遇到的某一或一系列无法预知的堵塞事件对决策者路径选择策略的影响,考虑堵塞只发生在一条特殊路径上且可恢复的情况,采用局内竞争分析的思想,建立了局内车辆路径问题的数学模型,对车辆到达堵塞点时堵塞恢复时间未知这一情形下的路径选择问题,提出了两种混合策略,给出了相应的竞争比,并对其竞争性能进行了理论分析。

关键词: 运筹学, 混合策略, 竞争分析, 局内车辆路径问题, 恢复时间未知

Abstract: This paper studies the vehicle routing problem with a series of unexpected congested nodes. First, an online model is formulated for the case that the congested nodes only occur on a special road. It is assumed that a congested node can only be known after the vehicle reaches it, and its recovery time is uncertain (i.e., the information about both the congested node and its recovery time is released in an online fashion). After that, two mixed strategies are proposed to address the problem. Furthermore, the competitive analysis of these two strategies and their competitive ratios are provided.

Key words: operational research, mixed strategy, competitive analysis, online vehicle routing problem, unknown recovery time

中图分类号:

F224.31

马卫民, 董丹丹, 王珂. 基于特殊路径的局内车辆路径问题混合策略研究[J]. 运筹与管理, 2011, 20(5): 57-62.

MA Wei-min, DONG Dan-Dan, WANG Ke. Mixed Strategies for the Online Vehicle Routing Problem on a Special Road[J]. Operations Research and Management Science, 2011, 20(5): 57-62.

参考文献

[1] Dantzig G, Ramser J. The truck dispatching problem[J]. Management Science, 1959, (6): 80-91.
[2] Sleator D D, Tarjan R E. Amortized efficiency of list update and paging rules[J]. Communications of the ACM, 1985, 28: 202-208.
[3] Manasse M S, McGeoch L A, Sleator D D. Competitive algorithms for server problems[J]. Journal of Algorithms, 1990, 11 (2): 208-230.
[4] David S B, Borodin A. A new measure for the study of the on-line algorithm[J]. Algorithmica, 1994, 11 (1): 73-91.
[5] Koutsoupias E, Papadimitriou C. On the k-server conjecture[J]. Journal of ACM, 1995, 42(5): 971-983.
[6] Alon N, Karp R M, Peleg D, et al. A graph-theoretic game and its application to the k-server problem[J]. SIAM Journal on Computing, 1995, 24(1): 78-100.
[7] 马卫民,王刊良.局内管理决策问题及其竞争策略[J].管理科学学报,2003,6(2):29-34.
[8] 徐维军,徐寅峰,卢致杰,徐金红.占线决策问题及竞争分析方法[J].系统工程,2005,23(5):106-110.
[9] EI-Yaniv R, Kaniel R, Linial N. Competitive optimal on-line leasing[J]. Algorithmica, 1999, 25: 116-140.
[10] Ausiello G, Feuerstein E, et al. Algorithms for the on-line travelling salesman[J]. Algorithmica, 2001, 29: 560-581.
[11] Bose P, Morin P. Online routing in triangulations[J]. SIAM Journal on Computing, 2004, 33(4): 937-951.
[12] Feuerstein E, Stougie L. On-line single-server dial-a-ride problems[J]. Theoretical Computer Science, 2001, 268(1): 91-105.
[13] 朱志军,徐寅峰,刘春草.局内车辆选线问题和竞争策略分析[J].系统工程学报,2003,18(4):324-330.
[14] 胡茂林.局内车辆选线问题的比较策略及其竞争比分析[J].宁夏大学学报,2005,26(3):207-210.
[15] 胡茂林,徐寅峰,徐维军.堵塞点可恢复型在线运输车辆的调度策略研究[J].系统工程学报,2006,21(5):484-489.
[16] 苏兵,徐寅峰.运输过程中路径突发堵塞事件对策研究[J].预测,2005,24(2):76-80.