AASCIT - Journal - All Issues

ISSN Print: 2381-1218 ISSN Online: 2381-1226

Computational and Applied Mathematics Journal

The Journal

Manuscript Information

Research on the Hybrid Fruit Fly Optimization Algorithm with Local Search for Multi-compartment Vehicle Routing Problem

Computational and Applied Mathematics Journal
Vol.3 , No. 4, Publication Date: Aug. 30, 2017, Page: 22-31

597 Views Since August 30, 2017, 588 Downloads Since Aug. 30, 2017

Paper in PDF (391K)

Follow on

Authors

[1]	Li Shouwei, School of Business, Shandong Normal University, Ji'nan, China.

Abstract

With the rapid development of modern logistics industry, multi-compartment vehicle routing problem (MCVRP) is one of the research directions of vehicle routing problem, mainly to solve the problem of the transportation of non-mixed products in one vehicle. These products must be stored in separate compartments, and should not exceed the capacity of the carriage. A hybrid fruit fly optimization algorithm (HFOA) is proposed to solve the multi-compartment vehicle routing problem with capacity constraints, which combines three local search methods: 2-OPT, Swap and Insert. In HFOA, firstly, the initial feasible solution of MCVRP is constructed by using the stochastic method. Secondly, from the initial solution, the path probability function is used to create the fruit fly path. Then, three local search methods are used to optimize the path, and the optimal solution is used to update the trajectory strength of the distribution network. To improve the search efficiency, the local search process is only implemented in one iteration. Based on the simulation results of 7 benchmark problem, it is found that the HFOA algorithm can produce better path planning than traditional methods.

Keywords

Vehicle Routing Problem, Multi-compartment Vehicle, Fruit Fly Optimization Algorithm, Local Search

Reference

[01]	Dantzig G B, Ramser J H. The truck dispatching problem [J]. Management science, 1959, 6(1): 80-91.
[02]	Garey M R, Johnson D S. Computers and Intractability: A Guide to the Theory of NP-Completeness [M]. W. H. Freeman, 1979.
[03]	Pan W T. A new fruit fly optimization algorithm: taking the financial distress model as an example [J]. Knowledge-Based Systems, 2012, 26: 69-74.
[04]	Wang X. L., etc. A hybrid discrete fruit fly optimization algorithm for solving permutation flow-shop scheduling problem [J]. Control Theory & Applications, 2014, 31(2):159-164.
[05]	Cheng H., Liu C. Z. Mixed Fruit Fly Optimization Algorithm Based on Chaotic Mapping [J]. Computer Engineering, 2013, 39(5):218-221.
[06]	Han J. Y., Liu C. Z. Fruit fly optimization algorithm based on bacterial chemotaxis [J]. Journal of Computer Application, 2013, 33(4):964-966.
[07]	Chajakis E D, Guignard M. Scheduling deliveries in vehicles with multiple compartments [J]. Journal of Global Optimization, 2003, 26(1): 43-78.
[08]	Avella P, Boccia M, Sforza A. Solving a fuel delivery problem by heuristic and exact approaches [J]. European Journal of Operational Research, 2004, 152(1): 170-179.
[09]	El Fallahi A, Prins C, Calvo R W. A memetic algorithm and a tabu search for the multi-compartment vehicle routing problem [J]. Computers & Operations Research, 2008, 35(5): 1725-1741.
[10]	Chen P., Huang H. K., Dong X. Y. A multi-operator based iterated local search algorithm for the capacitated vehicle routing problem [J]. Journal of Beijing Jiaotong University, 2009, 33(2):1-5.
[11]	Muyldermans L, Pang G. On the benefits of co-collection: Experiments with a multi-compartment vehicle routing algorithm [J]. European Journal of Operational Research, 2010, 206(1): 93-103.
[12]	Reed M, Yiannakou A, Evering R. An ant colony algorithm for the multi-compartment vehicle routing problem [J]. Applied Soft Computing, 2014, 15: 169-176.
[13]	Gajpal Y, Abad P. An ant colony system (ACS) for vehicle routing problem with simultaneous delivery and pickup [J]. Computers & Operations Research, 2009, 36(12): 3215-3223.
[14]	Balseiro S R, Loiseau I, Ramonet J. An ant colony algorithm hybridized with insertion heuristics for the time dependent vehicle routing problem with time windows [J]. Computers & Operations Research, 2011, 38(6): 954-966.
[15]	Jair J, Paternina-Arboleda C D, Cantillo V, et al. A two-pheromone trail ant colony system—tabu search approach for the heterogeneous vehicle routing problem with time windows and multiple products [J]. Journal of Heuristics, 2013, 19(2): 233-252.
[16]	TAN Wei WEN Qing To Solve the Pickup Delivery Vehicle Routing Vrpspd Problem Based on Ant System and 2-opt Method [J]. Mathematics in Practice and Theory, 2015(24):235-242.
[17]	Liu Z. X., Wang Y. F., Zhang Y. Multiple Population Fruit Fly Optimization Algorithm for Automatic Warehouse Order Picking Operation Scheduling Problem [J]. Journal of Wuhan University of Technology, 2014, 36(3): 71-77.
[18]	Zheng X. L., Wang L., Wang S. Y. A hybrid discrete fruit fly optimization algorithm for solving permutation flow-shop scheduling problem [J]. Control Theory ＆ Applications, 2014, 31(2):159-164.
[19]	Lin S. Computer solutions of the traveling salesman problem [J]. The Bell System Technical Journal, 1965, 44(10): 2245-2269.
[20]	Laporte G. The vehicle routing problem: An overview of exact and approximate algorithms [J]. European Journal of Operational Research, 1992, 59(3): 345-358.
[21]	Lin S W, Lee Z J, Ying K C, et al. Applying hybrid meta-heuristics for capacitated vehicle routing problem [J]. Expert Systems with Applications, 2009, 36(2): 1505-1512.
[22]	Abdulkader M M S, Gajpal Y, ElMekkawy T Y. Hybridized ant colony algorithm for the Multi Compartment Vehicle Routing Problem[J]. Applied Soft Computing, 2015, 37: 196-203.