带有异质固定车队的能力约束弧路径问题

摘要/Abstract

摘要： 研究了带有异质固定车队的能力约束弧路径问题(CARP).为了在可接受时间里求得较理想的解，提出了基于Route-First, Cluster-Second思想的两阶段启发式算法，并使用局域搜索(LS)和加强的局域搜索(ELS)进行改善. 基于标准CARP算例生成了 HFFCARP测试数据，算法结果表明了LS和ELS的有效性，且ELS具有更好的效果.

关键词: 能力约束弧路径问题, , , 异质固定车队, 启发式算法, 加强的局域搜索

Abstract: The heterogeneous fixed fleet capacitated arc routing problem (HFFCARP) is a generalization of the CARP, which is with several vehicle types, each type being defined by a capacity, a fixed cost and a cost per distance unit. In order to solve this new NP-hard problem in acceptable time, two-stage heuristics based on route-first, cluster-second were proposed and local search (LS) and enhanced local search (ELS) were proposed to improve the results. The HFFCARP data generated from the CARP benchmark instances were tested and the results show that the heuristics improved by LS and ELS are effective to solve the HFFCARP, and ELS improves the results much more significantly.

Key words: capacitated arc routing problem(CARP), heterogeneous fixed fleet, heuristics, enhanced local search(ELS)

中图分类号:

TP 301

刘天堂, 江志斌, 耿娜, 刘冉, 刘树军. 带有异质固定车队的能力约束弧路径问题[J]. 上海交通大学学报（自然版）, 2012, 46(11): 1759-1763.

LIU Tian-Tang, JIANG Zhi-Bin, GENG Na, LIU Ran, LIU Shu-Jun. The Heterogeneous Fixed Fleet Capacitated Arc Routing Problem[J]. Journal of Shanghai Jiaotong University, 2012, 46(11): 1759-1763.

参考文献

［1］Golden B L, Wong R T. Capacitated arc routing problems［J］. Networks, 1981, 11(3): 305315.
［2］Golden J, DeArmon J S, Baker E K. Computational experiments with algorithms for a class of routing problems［J］. Computers & Operations Research, 1983, 10(1): 4759.
［3］Ulusoy G. The fleet size and mix problem for capacitated arc routing［J］. European Journal of Operational Research, 1985, 22(3): 329337.
［4］Hertz A, Laporte G, Mittaz M. A tabu search heuristic for the capacitated arc routing problem［J］. Operations Research, 2000, 48(1): 129135.
［5］Brando J, Eglese R. A deterministic tabu search algorithm for the capacitated arc routing problem［J］. Computers & Operations Research, 2008, 35(4): 11121126.
［6］Hertz A, Mittaz M. A variable neighborhood descent algorithm for the undirected capacitated arc routing problem［J］. Transportation Science, 2001, 35(4): 425434.
［7］Beullens P, Muyldermans L, Cattrysse D, et al. A guided local search heuristic for the capacitated arc routing problem［J］. European Journal of Operational Research, 2003, 147(3): 629643.
［8］Lacomme P, Prins C, RamdaneCherif W. Competitive memetic algorithms for arc routing problems［J］. Annals of Operations Research, 2004, 131(1): 159185.
［9］Santos L, CoutinhoRodrigues J, Current J R. An improved ant colony optimization based algorithm for the capacitated arc routing problem［J］. Transportation Research Part B: Methodological, 2010, 44(2): 246266.
［10］Chu F, Labadi N, Prins C. A scatter search for the periodic capacitated arc routing problem［J］. European Journal of Operational Research, 2006, 169(2): 586605.
［11］Lacomme P, Prins C, Sevaux M. A genetic algorithm for a biobjective capacitated arc routing problem［J］. Computers & Operations Research, 2006, 33(12): 34733493.
［12］Belenguer J M, Benavent E, Labadi N, et al. Splitdelivery capacitated arcrouting problem: Lower bound and metaheuristic ［J］. Transportation Science, 2010, 44(2): 206220.
［13］Laporte G, Musmanno R, Vocaturo F. An adaptive large neighbourhood search heuristic for the capacitated arcrouting problem with stochastic demands［J］. Transportation Science, 2010, 44(1): 125135.
［14］Frederickson G. Approximation algorithms for some postman problems［J］. Journal of the ACM (JACM), 1979, 26(3): 538554.

[1]	王聚团, 戚晓宁, 黄志明. 水下生产管汇测试技术及其改进研究[J]. 海洋工程装备与技术, 2022, 9(2): 43-49.
[2]	袁振钦, 邹科, 孙亚峰, 刘刚, 屈衍, 李居跃. 基于时域分析法的动态电缆疲劳分析[J]. 海洋工程装备与技术, 2022, 9(2): 50-55.
[3]	王娟, 杨明旺, 郑茂尧, 刘凌云, 赵立君. 高强钢在大型半潜式平台组块建造中的应用[J]. 海洋工程装备与技术, 2022, 9(1): 27-31.
[4]	陈欣, 赵晓磊, 王立坤, 肖德明, 张腾月. 深水大型吸力锚建造技术研究[J]. 海洋工程装备与技术, 2022, 9(1): 32-36.
[5]	尹彦坤, 易涤非. 半潜式生产平台船体结构关键节点工程临界评估[J]. 海洋工程装备与技术, 2022, 9(1): 52-57.
[6]	ZHANG Shengfa (张胜发), TANG Na (唐纳), SHEN Guofeng (沈国峰), WANG Han (王悍), QIAO Shan (乔杉). Universal Software Architecture of Magnetic Resonance-Guided Focused Ultrasound Surgery System and Experimental Study[J]. J Shanghai Jiaotong Univ Sci, 2021, 26(4): 471-481.
[7]	MA Qunsheng (马群圣), CEN Xingxing (岑星星), YUAN Junyi (袁骏毅), HOU Xumin (侯旭敏). Word Embedding Bootstrapped Deep Active Learning Method to Information Extraction on Chinese Electronic Medical Record[J]. J Shanghai Jiaotong Univ Sci, 2021, 26(4): 494-502.
[8]	KONG Xiangqiang (孔祥强), MENG Xiangxi (孟祥熙), LI Jianbo (李见波), SHANG Yanping (尚燕平), CUI Fulin (崔福林) . Comparative Study on Two-Stage Absorption Refrigeration Systems with Different Working Pairs[J]. J Shanghai Jiaotong Univ Sci, 2021, 26(2): 155-162.
[9]	ZHUANG Weimin (庄蔚敏), WANG Pengyue (王鹏跃), AO Wenhong (熬文宏), CHEN Gang (陈刚) . Experiment and Simulation of Impact Response of Woven CFRP Laminates with Different Stacking Angles[J]. J Shanghai Jiaotong Univ Sci, 2021, 26(2): 218-230.
[10]	安庆升, 孙立东, 武秋生. 碳纤维增强复合材料发射筒设计研究[J]. 空天防御, 2021, 4(2): 13-.
[11]	ZHOU Xuhui (周旭辉), ZHANG Wenguang (张文光), XIE Jie (谢颉). Effects of Micro-Milling and Laser Engraving on Processing Quality and Implantation Mechanics of PEG-Dexamethasone Coated Neural Probe[J]. J Shanghai Jiaotong Univ Sci, 2021, 26(1): 1-9.
[12]	HUANG Ningning (黄宁宁), MA Yixin (马艺馨), ZHANG Mingzhu (张明珠), GE Hao (葛浩), WU Huawei (吴华伟). Finite Element Modeling of Human Thorax Based on MRI Images for EIT Image Reconstruction[J]. J Shanghai Jiaotong Univ Sci, 2021, 26(1): 33-39.
[13]	WANG Xianjin, GAO Xu, YU Kuigang . Fixture Locating Modelling and Optimization Research of Aluminum Alloy Sidewall in a High-Speed Train Body[J]. J Shanghai Jiaotong Univ Sci, 2020, 25(6): 706-713.
[14]	QIAO Xing, MA Dan, YAO Xuliang, FENG Baolin. Stability and Numerical Analysis of a Standby System[J]. J Shanghai Jiaotong Univ Sci, 2020, 25(6): 769-778.
[15]	WU Jin, MIN Yu, YANG Xiaodie, MA Simin . Micro-Expression Recognition Algorithm Based on Information Entropy Feature[J]. Journal of Shanghai Jiao Tong University(Science), 2020, 25(5): 589-599.