通过引入养护时间的有界不确定性集合，建立了路径规划问题的鲁棒优化模型，以使总服务成本最小化.设计开发分支切割算法，对该问题进行精确性求解.通过蒙特卡罗模拟法从总服务成本和服务水平两方面对解的鲁棒性进行评价，并对方案的鲁棒性水平进行敏感性分析.实验表明，利用鲁棒优化模型得到的解对服务时间偏差的敏感性较低.
This paper studies the vehicle routing problem for daily maintenance operations of a road network suffered from the uncertainty of service time. A robust optimization model is formulated to minimize total cost and the optimal problem is solved by the branch-and-cut method. In computational experiments, the performances of the robust solutions are analyzed using Monte Carlo simulation. The experimental analysis demonstrates that the robust optimization approach can yield routes that minimize total cost and are less sensitive to substantial deviations of service times. Decision makers may obtain some managerial insights from robust optimization solution to determine an appropriate routing strategy.
［1］KAO E P C. A preference order dynamic program for a stochastic traveling salesman problem［J］. Operations Research, 1978, 26(6): 1033-1045.
［2］TAGMOUTI M, GENDREAU M, POTVIN J Y. A dynamic capacitated arc routing problem with time-dependent service costs［J］. Transportation Research Part C: Emerging Technologies, 2011, 19(1): 20-28.
［3］葛显龙, 王旭, 邓蕾. 基于联合配送的开放式动态车辆路径问题及算法研究［J］. 管理工程学报, 2013 (3): 60-68.
GE Xianlong, WANG Xu, DENG Lei. Open dynamic vehicle routing problem and algorithms based on joint distribution［J］. Journal of Industrial Engineering and Engineering Management, 2013 (3): 60-68.
［4］LI X, TIAN P, LEUNG S C H. Vehicle routing problems with time windows and stochastic travel and service times: Models and algorithm［J］. International Journal of Production Economics, 2010, 125(1): 137-145.
［5］MENDOZA J E, CASTANIER B, GURET C, et al. A memetic algorithm for the multi-compartment vehicle routing problem with stochastic demands［J］. Computers and Operations Research, 2010, 37(11): 1886-1898.
［6］ARCHETTI C, BIANCHESSI N, SPERANZA M G. Branch-and-cut algorithms for the split delivery vehicle routing problem［J］. European Journal of Operational Research, 2014, 238(3): 685-698.
［7］孙锡梅, 林丹.同时配送和回收需求的带容量约束弧路径问题［J］. 计算机应用, 2013, 33(A01): 62-65.
SUN Ximei, LIN Dan. Capacitated arc routing problem with simultaneous pickup and delivery［J］. Journal of Computer Applications, 2013, 33(A01): 62-65.
［8］刘洁, 何彦锋. 城市垃圾收集车辆弧路径问题研究［J］.成都大学学报(自然科学版), 2013, 32(4): 423-426.
LIU Jie, HE Yanfeng. Municipal refuse collection vehicle routing problem［J］. Journal of Chengdu University (Nature Science Edition), 2013, 32(4): 423-426.
［9］BEN-TAL A, NEMIROVSKI A. Robust convex optimization［J］. Mathematics of Operations Research, 1998, 23(4): 769-805.
［10］BEN-TAL A, NEMIROVSKI A. Robust solutions of uncertain linear programs［J］. Operations Research Letters, 1999, 25(1): 1-13.
［11］BERTSIMAS D, SIM M. The price of robustness［J］. Operations Research, 2004, 52(1): 35-53.
［12］GHAOUI L E, OKS M, OUSTRY F. Worst-case value-at-risk and robust portfolio optimization: A conic programming approach［J］. Operations Research, 2003, 51(4): 543-556.
［13］GOLDFARB D, IYENGAR G. Robust portfolio selection problems［J］. Mathematics of Operations Research, 2003, 28(1): 1-38.
［14］ALEM D J, MORABITO R. Production planning in furniture settings via robust optimization［J］. Computers and Operations Research, 2012, 39(2): 139-150.
［15］VARAS M, MATURANA S, PASCUAL R, et al. Scheduling production for a sawmill: A robust optimization approach［J］. International Journal of Production Economics, 2014, 150: 37-51.
［16］BERTSIMAS D, THIELE A. A robust optimization approach to supply chain management［C］∥International Conference on Integer Programming and Combinatorial Optimization. Berlin: Springer Berlin Heidelberg, 2004: 86-100.
［17］TAL A B, GOLANY B, NEMIROVSKI A, et al. Supplier-retailer flexible commitments contracts: A robust optimization approach［J］. Manufacturing and Service Operations Management, 2011, 7(3): 248-271.
［18］SUNGUR I, ORDNEZ F, DESSOUKY M. A robust optimization approach for the capacitated vehicle routing problem with demand uncertainty［J］. IIE Transactions, 2008, 40(5): 509-523.
［19］AGRA A, CHRISTIANSEN M, FIGUEIREDO R, et al. The robust vehicle routing problem with time windows［J］. Computers and Operations Research, 2013, 40(3): 856-866.
［20］麻存瑞, 马昌喜. 不确定环境中危险品运输路径鲁棒优化［J］. 中国安全科学学报, 2014, 24(3): 91-96.
MA Cunrui, MA Changxi. Robust optimization of hazardous materials transportation route in uncertain environment［J］. China Safety Science Journal, 2014, 24(3): 91-96.
［21］钟石泉, 马寿峰. 车辆路径问题的改进分支切割法［J］. 系统工程理论与实践, 2009, 29(10): 152-158.
ZHONG Shiquan, MA Shoufeng. Improved branch and cut algorithm for vehicle routing problem［J］. Systems Engineering — Theory and Practice, 2009, 29(10): 152-158.
