A Discrete Fruit Fly Optimization Algorithm for the Capacitated Vehicle Routing Problem
详细信息 查看官网全文
- 英文论文题名：A Discrete Fruit Fly Optimization Algorithm for the Capacitated Vehicle Routing Problem
- 论文作者：LU Jia-wen ; WANG Ling ; JIANG En-da
- 英文论文作者：LU Jia-wen ; WANG Ling ; JIANG En-da ; Department of Automation ; Tsinghua University
- 年：2017
- 作者机构：Department of Automation,Tsinghua University;
- 英文论文关键词：capacitated vehicle routing problem ; fruit fly optimization algorithm ; specific feature ; elimination mechanism
- 会议召开时间：2017-07-26
- 会议录名称：第36届中国控制会议论文集（B）
- 英文会议录名称：Proceedings of the 36th Chinese Control Conference（B）
- 语种：英文
- 分类号：TP18
- 学会代码：KZLL
- 会议名称：第36届中国控制会议
- 会议地点：中国辽宁大连
- 主办单位：中国自动化学会控制理论专业委员会
- 学会名称：中国自动化学会控制理论专业委员会
- 页数：6
- 文件大小：324k
- 原文格式：D
- 会议级别：全国
摘要
In this paper, a discrete fruit fly optimization algorithm(DFOA) is proposed for solving the capacitated vehicle routing problem(CVRP). Firstly, a two-part discrete array is presented to represent the solution. Secondly, the initialization based on K-means is proposed to take full use of the location information of the customers. The customers in each cluster are allocated to one vehicle. Meanwhile, the repair operation is designed for not taking the capacity constraint into account in the initialization. Due to the characteristics of the CVRP, it may be effective to exchange or reallocate the customers between the neighbor routes in the graph. Thus, the smell-based search and vision-based search with the specific problem feature are designed. Moreover, the elimination mechanism and the simulated annealing based search are used to balance the exploration and the exploitation capabilities. In addition, the effect of parameter setting is investigated by using the Taguchi method of design-of-experiment to obtain the suitable values. Finally, numerical tests with the benchmark instances are carried out, which demonstrate the effectiveness of the proposed algorithm.
In this paper, a discrete fruit fly optimization algorithm(DFOA) is proposed for solving the capacitated vehicle routing problem(CVRP). Firstly, a two-part discrete array is presented to represent the solution. Secondly, the initialization based on K-means is proposed to take full use of the location information of the customers. The customers in each cluster are allocated to one vehicle. Meanwhile, the repair operation is designed for not taking the capacity constraint into account in the initialization. Due to the characteristics of the CVRP, it may be effective to exchange or reallocate the customers between the neighbor routes in the graph. Thus, the smell-based search and vision-based search with the specific problem feature are designed. Moreover, the elimination mechanism and the simulated annealing based search are used to balance the exploration and the exploitation capabilities. In addition, the effect of parameter setting is investigated by using the Taguchi method of design-of-experiment to obtain the suitable values. Finally, numerical tests with the benchmark instances are carried out, which demonstrate the effectiveness of the proposed algorithm.
In this paper, a discrete fruit fly optimization algorithm(DFOA) is proposed for solving the capacitated vehicle routing problem(CVRP). Firstly, a two-part discrete array is presented to represent the solution. Secondly, the initialization based on K-means is proposed to take full use of the location information of the customers. The customers in each cluster are allocated to one vehicle. Meanwhile, the repair operation is designed for not taking the capacity constraint into account in the initialization. Due to the characteristics of the CVRP, it may be effective to exchange or reallocate the customers between the neighbor routes in the graph. Thus, the smell-based search and vision-based search with the specific problem feature are designed. Moreover, the elimination mechanism and the simulated annealing based search are used to balance the exploration and the exploitation capabilities. In addition, the effect of parameter setting is investigated by using the Taguchi method of design-of-experiment to obtain the suitable values. Finally, numerical tests with the benchmark instances are carried out, which demonstrate the effectiveness of the proposed algorithm.
引文
[1]Made in China 2025.(2015).[Online].Available:http://www.gov.cn/zhengce/content/2015-05/19/content_9784.htm
[2]P.Toth,D.Vigo,Vehicle routing:problems,methods,and applications.Philadelphia:Siam,2014.
[3]R.Baldacci,E.Hadjiconstantinou,A.Mingozzi,An exact algorithm for the capacitated vehicle routing problem based on a two-commodity network flow formulation,Operations Research,52(5):723-738,2004.
[4]R.Baldacci,N.Christofide,A.Mingozzi,An exact algorithm for the vehicle routing problem based on the set partitioning formulation with additional cuts,Mathematical Programming,115(2):351-385,2008.
[5]R.Fukasawa,H.Longo,J.Lysgaard,Robust branchand-cut-and-price for the capacitated vehicle routing problem,Mathematical Programming,106(3):491-511,2006.
[6]G.Clarke,J.W.Wright.Scheduling of vehicles from a central depot to a number of delivery points,Operations Research,12(4):568-581,1964.
[7]B.E.Gillett,L.R.Miller,A heuristic algorithm for the vehicle-dispatch problem,Operations Research,22(2):340-349,1974.
[8]L.D.Bodin,S.J.Kursh,A computer-assisted system for the routing and scheduling of street sweepers,Operations Research,26(4):525-537,1978.
[9]W.Y.Szeto,Y.Wu,S.C.Ho.An artificial bee colony algorithm for the capacitated vehicle routing problem,European J of Operational Research,215(1):126-135,2011.
[10]S.Mazzeo,I.Loiseau,An ant colony algorithm for the capacitated vehicle routing,Electronic Notes in Discrete Mathematics,18:181-186,2004.
[11]E.Teymourian,V.Kayvanfar,G.H.M.Komaki,Enhanced intelligent water drops and cuckoo search algorithms for solving the capacitated vehicle routing problem,Information Sciences,334:354-378,2016.
[12]W.T.Pan,A new fruit fly optimization algorithm:taking the financial distress model as an example,Knowledge-Based Systems,26:69-74,2012.
[13]X.L.Zheng,L.Wang,S.Y.Wang,A novel fruit fly optimization algorithm for the semiconductor final testing scheduling problem,Knowledge-Based Systems,57:95-103,2014.
[14]X.L.Zheng,L.Wang,S.Y.Wang,A hybrid discrete fruit fly optimization algorithm for solving permutation flow-shop scheduling problem,Control Theory&Applications,31(5):159-164,2014.
[15]J.Li,Q.Pan,K.Mao,Solving the steelmaking casting problem using an effective fruit fly optimization algorithm,Knowledge-Based Systems,72:28-36,2014.
[16]G.Laporte,The vehicle routing problem:An overview of exact and approximate algorithms,European Journal of Operational Research,59(3):345-358,1992.
[17]A.E.Carter,C.T.Ragsdale,A new approach to solving the multiple traveling salesperson problem using genetic algorithms,European Journal of Operational Research,175(1):246-257,2006.
[18]L.Wang,Intelligent optimization algorithms with applications,Beijing:Tsinghua Univ.,2001.
[19]D.C.Montgomery,Design and analysis of experiment.Arizona:John Wiley&Sons,2008.
[20]Y.Zhao,Double populations genetic algorithm for vehicle routing problem,Computer Integrated Manufacturing Systems,10(3):303-306,2004.
[21]J.M.Xiao,J.J Li,X.H.Wang.Modified particle swarm optimization algorithm for vehicle routing problem,Computer Integrated Manufacturing Systems,11(4):577-581,2005.
[22]Z.Z.Jiang,D.W.Wang.Predatory search algorithm for vehicle routing problem.Computer Integrated Manufacturing Systems,12(11):1899-1908,2006.
[23]Y.W.Zhao,D.J.Peng,J.L Zhang,Quantum evolutionary algorithm for capacitated vehicle routing problem,Systems Engineering-Theory&Practice,29(2):159-166,2009.
[24]C.H.Jiang,S.G.Dai,Y.H.Hu,Hybrid genetic algorithm for capacitated vehicle routing problem,Computer Integrated Manufacturing System,13(10):2047-2052,2007.
[25]P.D.Wang,G.Y.Tang,Y.Li,Improved ant colony algorithm for capacitated vehicle routing problems,Control and Decision,27(11):1633-1638,2012.
[26]J.C.Goodson,J.W.Ohlmann,B.W.Thomas,Cyclic-order neighborhoods with application to the vehicle routing problem with stochastic demand,European J of Operational Research,217(2):312-323,2012.
[27]T.Tlili,S.Faiz,S.Krichen,A hybrid metaheuristic for the distance-constrained capacitated vehicle routing problem,Procedia-Social and Behavioral Sciences,109:779-783,2014.
[2]P.Toth,D.Vigo,Vehicle routing:problems,methods,and applications.Philadelphia:Siam,2014.
[3]R.Baldacci,E.Hadjiconstantinou,A.Mingozzi,An exact algorithm for the capacitated vehicle routing problem based on a two-commodity network flow formulation,Operations Research,52(5):723-738,2004.
[4]R.Baldacci,N.Christofide,A.Mingozzi,An exact algorithm for the vehicle routing problem based on the set partitioning formulation with additional cuts,Mathematical Programming,115(2):351-385,2008.
[5]R.Fukasawa,H.Longo,J.Lysgaard,Robust branchand-cut-and-price for the capacitated vehicle routing problem,Mathematical Programming,106(3):491-511,2006.
[6]G.Clarke,J.W.Wright.Scheduling of vehicles from a central depot to a number of delivery points,Operations Research,12(4):568-581,1964.
[7]B.E.Gillett,L.R.Miller,A heuristic algorithm for the vehicle-dispatch problem,Operations Research,22(2):340-349,1974.
[8]L.D.Bodin,S.J.Kursh,A computer-assisted system for the routing and scheduling of street sweepers,Operations Research,26(4):525-537,1978.
[9]W.Y.Szeto,Y.Wu,S.C.Ho.An artificial bee colony algorithm for the capacitated vehicle routing problem,European J of Operational Research,215(1):126-135,2011.
[10]S.Mazzeo,I.Loiseau,An ant colony algorithm for the capacitated vehicle routing,Electronic Notes in Discrete Mathematics,18:181-186,2004.
[11]E.Teymourian,V.Kayvanfar,G.H.M.Komaki,Enhanced intelligent water drops and cuckoo search algorithms for solving the capacitated vehicle routing problem,Information Sciences,334:354-378,2016.
[12]W.T.Pan,A new fruit fly optimization algorithm:taking the financial distress model as an example,Knowledge-Based Systems,26:69-74,2012.
[13]X.L.Zheng,L.Wang,S.Y.Wang,A novel fruit fly optimization algorithm for the semiconductor final testing scheduling problem,Knowledge-Based Systems,57:95-103,2014.
[14]X.L.Zheng,L.Wang,S.Y.Wang,A hybrid discrete fruit fly optimization algorithm for solving permutation flow-shop scheduling problem,Control Theory&Applications,31(5):159-164,2014.
[15]J.Li,Q.Pan,K.Mao,Solving the steelmaking casting problem using an effective fruit fly optimization algorithm,Knowledge-Based Systems,72:28-36,2014.
[16]G.Laporte,The vehicle routing problem:An overview of exact and approximate algorithms,European Journal of Operational Research,59(3):345-358,1992.
[17]A.E.Carter,C.T.Ragsdale,A new approach to solving the multiple traveling salesperson problem using genetic algorithms,European Journal of Operational Research,175(1):246-257,2006.
[18]L.Wang,Intelligent optimization algorithms with applications,Beijing:Tsinghua Univ.,2001.
[19]D.C.Montgomery,Design and analysis of experiment.Arizona:John Wiley&Sons,2008.
[20]Y.Zhao,Double populations genetic algorithm for vehicle routing problem,Computer Integrated Manufacturing Systems,10(3):303-306,2004.
[21]J.M.Xiao,J.J Li,X.H.Wang.Modified particle swarm optimization algorithm for vehicle routing problem,Computer Integrated Manufacturing Systems,11(4):577-581,2005.
[22]Z.Z.Jiang,D.W.Wang.Predatory search algorithm for vehicle routing problem.Computer Integrated Manufacturing Systems,12(11):1899-1908,2006.
[23]Y.W.Zhao,D.J.Peng,J.L Zhang,Quantum evolutionary algorithm for capacitated vehicle routing problem,Systems Engineering-Theory&Practice,29(2):159-166,2009.
[24]C.H.Jiang,S.G.Dai,Y.H.Hu,Hybrid genetic algorithm for capacitated vehicle routing problem,Computer Integrated Manufacturing System,13(10):2047-2052,2007.
[25]P.D.Wang,G.Y.Tang,Y.Li,Improved ant colony algorithm for capacitated vehicle routing problems,Control and Decision,27(11):1633-1638,2012.
[26]J.C.Goodson,J.W.Ohlmann,B.W.Thomas,Cyclic-order neighborhoods with application to the vehicle routing problem with stochastic demand,European J of Operational Research,217(2):312-323,2012.
[27]T.Tlili,S.Faiz,S.Krichen,A hybrid metaheuristic for the distance-constrained capacitated vehicle routing problem,Procedia-Social and Behavioral Sciences,109:779-783,2014.