A hybrid discrete artificial bee colony for the green pickup and delivery problem with time windows
Abstract
This paper formulates a new optimization pickup and delivery problem with time windows which take into account the CO2 emission. This new NP-hard combinatorial optimization problem is called green pickup and delivery problem with time windows (GPDPTW), the recent developments in the vehicle routing problem and its variants, which extends PDP and PDPTW with respect to several constraints. The objective is to find a set of routes for a fleet of vehicles in order to serve given transportation requests with a minimization of fuel consumption and CO2 emission to ensure the preservation of a clean and green environment. This paper presents a mathematical formulation and proposes a hybrid discrete artificial bee colony algorithm (HDABC) as a meta-heuristic algorithm which combines a discrete artificial bee colony with neighborhood operators to solve GPDPTW model. To the best of our knowledge, this is the first time that an emission of CO2 for the PDPTW is proposed. We performed computational experiments to evaluate the effectiveness of these proposed method, which provides the best result and can effectively find an optimal tour. Our results show that, (1) the shortest route is not necessarily the route that consumes the least of fuel; (2) the fuel consumption is affected by the load and the number of vehicles.
Full Text:
PDFReferences
B. Sahin, H. Yilmaz, Y. Ust, A. F. Guneri, et B. Gulsun, « An approach for analysing transportation costs and a case study », European Journal of Operational Research, vol. 193, no 1, p. 1-11, févr. 2009.
N. Christofides, A. Mingozzi, et P. Toth, The vehicle routing problem. Chichester; New York: Wiley, 1979.
P. Toth et D. Vigo, « The Vehicle Routing Problem », Éd. Philadelphia, PA, USA: Society for Industrial and Applied Mathematics, 2002, p. 1–26.
H. Xu, Z.-L. Chen, S. Rajagopal, et S. Arunapuram, « Solving a Practical Pickup and Delivery Problem », Transportation Science, vol. 37, no 3, p. 347-364, août 2003.
Y. Dumas, J. Desrosiers, et F. Soumis, « The pickup and delivery problem with time windows », European Journal of Operational Research, vol. 54, no 1, p. 7-22, sept. 1991.
M. Sol et M. W. P. Savelsbergh, « A branch-and-price algorithm for the pickup and delivery problem with time windows », Memorandum COSOR; Vol. 9422. Eindhoven: Technische Universiteit Eindhoven, 1994.
W. P. Nanry et J. Wesley Barnes, « Solving the pickup and delivery problem with time windows using reactive tabu search », Transportation Research Part B: Methodological, vol. 34, no 2, p. 107-121, févr. 2000.
M. M. Solomon, « Algorithms for the Vehicle Routing and Scheduling Problems with Time Window Constraints », Operations Research, vol. 35, no 2, p. 254-265, avril 1987.
H. Li et A. Lim, « A metaheuristic for the pickup and delivery problem with time windows », in Proceedings 13th IEEE International Conference on Tools with Artificial Intelligence. ICTAI 2001, 2001, p. 160-167.
H. C. Lau et Z. Liang, « Pickup and delivery with time windows: algorithms and test case generation », in Proceedings 13th IEEE International Conference on Tools with Artificial Intelligence. ICTAI 2001, 2001, p. 333-340.
H. Lim, A. Lim, et B. Rodrigues, « Solving the pickup and delivery problem with time windows USING “squeaky wheel” optimization with local search », 2002.
G. Pankratz, « A Grouping Genetic Algorithm for the Pickup and Delivery Problem with Time Windows », OR Spectrum, vol. 27, no 1, p. 21-41, janvier 2005.
G. Ding, L. Li, et Y. Ju, « Multi-strategy grouping genetic algorithm for the pickup and delivery problem with time windows », in Proceedings of the first ACM/SIGEVO Summit on Genetic and Evolutionary Computation - GEC ’09, Shanghai, China, 2009, p. 97.
Q. Lu et M. M. Dessouky, « A new insertion-based construction heuristic for solving the pickup and delivery problem with time windows », European Journal of Operational Research, vol. 175, no 2, p. 672-687, décembre 2006.
R. Bent et P. V. Hentenryck, « A two-stage hybrid algorithm for pickup and delivery vehicle routing problems with time windows », Computers & Operations Research, vol. 33, no 4, p. 875-893, avril 2006.
U. Derigs et T. Döhmer, « Indirect search for the vehicle routing problem with pickup and delivery and time windows », OR Spectrum, vol. 30, no 1, p. 149-165, janvier 2008.
S. Ropke et J.-F. Cordeau, « Branch and Cut and Price for the Pickup and Delivery Problem with Time Windows », Transportation Science, vol. 43, no 3, p. 267-286, juin 2009.
E. G. Carabetti, S. R. d Souza, M. C. P. Fraga, et P. H. A. Gama, « An Application of the Ant Colony System Metaheuristic to the Vehicle Routing Problem with Pickup and Delivery and Time Windows », in 2010 Eleventh Brazilian Symposium on Neural Networks, 2010, p. 176-181.
I. Harbaoui Dridi, R. Kammarti, M. Ksouri, et P. Borne, « Genetic Algorithm for Mulicriteria Optimization of a Multi-Pickup and Delivery Problem with Time Windows », in INCOM’09 IFAC, Russia, 2009, p. pp 1521-1526.
A. C. McKinnon et M. I. Piecyk, « Measurement of CO2 emissions from road freight transport: A review of UK experience », Energy Policy, vol. 37, no 10, p. 3733-3742, oct. 2009.
A. Sbihi et R. W. Eglese, « Combinatorial optimization and Green Logistics », 4OR, vol. 5, no 2, p. 99-116, juill. 2007.
T. Bektaş et G. Laporte, « The Pollution-Routing Problem », Transportation Research Part B: Methodological, vol. 45, no 8, p. 1232-1250, septembre 2011.
A. Palmer, « The development of an integrated routing and carbon dioxide emissions model for goods vehicles », Ph.D. Dissertation, School of Management, Cranfield University, novembre 2007.
İ. Kara, B. Y. Kara, et M. K. Yetis, « Energy Minimizing Vehicle Routing Problem », in Combinatorial Optimization and Applications, 2007, p. 62-71.
W. Maden, R. Eglese, et D. Black, « Vehicle routing and scheduling with time-varying data: A case study », Journal of the Operational Research Society, vol. 61, no 3, p. 515-522, mars 2010.
K. Fagerholt, « Optimal fleet design in a ship routing problem », International Transactions in Operational Research, vol. 6, no 5, p. 453-464, 1999.
Y. Xiao, Q. Zhao, I. Kaku, et Y. Xu, « Development of a fuel consumption optimization model for the capacitated vehicle routing problem », Computers & Operations Research, vol. 39, no 7, p. 1419-1431, juill. 2012.
Y. Kuo et C.-C. Wang, « Optimizing the VRP by minimizing fuel consumption », Management of Environmental Quality: An International Journal, juin 2011.
S. Zhang, C. K. M. Lee, K. L. Choy, W. Ho, et W. H. Ip, « Design and development of a hybrid artificial bee colony algorithm for the environmental vehicle routing problem », Transportation Research Part D: Transport and Environment, vol. 31, p. 85-99, août 2014.
J. Zhang, Y. Zhao, W. Xue, et J. Li, « Vehicle routing problem with fuel consumption and carbon emission », International Journal of Production Economics, vol. 170, p. 234-242, déc. 2015.
G. Poonthalir et R. Nadarajan, « A Fuel Efficient Green Vehicle Routing Problem with Varying Speed Constraint (F-GVRP) », Expert Syst. Appl., vol. 100, no C, p. 131–144, juin 2018.
R. Liu et Z. Jiang, « A constraint relaxation-based algorithm for the load-dependent vehicle routing problem with time windows », Flexible Services and Manufacturing Journal, vol. 31, no 2, p. 331-353, 2019.
O. Apaydin et M. T. Gonullu, « Emission control with route optimization in solid waste collection process: A case study », Sadhana, vol. 33, no 2, p. 71-82, avr. 2008.
V. Maraš, « Determining Optimal Transport Routes of Inland Waterway Container Ships », Transportation Research Record, vol. 2062, no 1, p. 50-58, janv. 2008.
S. Nanthavanij, P. Boonprasurt, W. Jaruphongsa, et V. Ammarapala, « Vehicle Routing Problem with Manual Materials Handling », In Proceeding of the 9th Asia Pacific industrial engineering and management system conference, Nusa Dua, Bali, Indonesia, 2008.
G. Tavares, Z. Zsigraiova, V. Semiao, et M. da G. Carvalho, « A case study of fuel savings through optimisation of MSW transportation routes », Management of Environmental Quality: An International Journal, juin 2008.
E. Demir, T. Bektaş, et G. Laporte, « An adaptive large neighborhood search heuristic for the Pollution-Routing Problem », European Journal of Operational Research, vol. 223, no 2, p. 346-359, décembre 2012.
E. Demir, T. Bektaş, et G. Laporte, « The bi-objective Pollution-Routing Problem », European Journal of Operational Research, vol. 232, no 3, p. 464-478, février 2014.
A. Franceschetti, D. Honhon, T. Van Woensel, T. Bektaş, et G. Laporte, « The time-dependent pollution-routing problem », Transportation Research Part B: Methodological, vol. 56, p. 265-293, octobre 2013.
R. Kramer, A. Subramanian, T. Vidal, et L. dos A. F. Cabral, « A matheuristic approach for the Pollution-Routing Problem », European Journal of Operational Research, vol. 243, no 2, p. 523-539, juin 2015.
Y. Xiao et A. Konak, « A simulating annealing algorithm to solve the green vehicle routing & scheduling problem with hierarchical objectives and weighted tardiness », Applied Soft Computing, vol. 34, p. 372-388, sept. 2015.
M. W. P. Savelsbergh et M. Sol, « The General Pickup and Delivery Problem », Transportation Science, vol. 29, no 1, p. 17-29, 1995.
S. Ubeda, F. J. Arcelus, et J. Faulin, « Green logistics at Eroski: A case study », International Journal of Production Economics, vol. 131, no 1, p. 44-51, mai 2011.
D. Karaboga, « An idea based on honey bee swarm for numerical optimization», Technical Report-TR06, Department of Computer Engineering, Engineering Faculty, Erciyes University, 2005.
D. Karaboga et B. Basturk, « On the performance of artificial bee colony (ABC) algorithm », Applied Soft Computing, vol. 8, no 1, p. 687-697, janvier 2008.
D. Karaboga et B. Akay, « A comparative study of Artificial Bee Colony algorithm », Applied Mathematics and Computation, vol. 214, no 1, p. 108-132, août 2009.
N. Karaboga, « A new design method based on artificial bee colony algorithm for digital IIR filters », Journal of the Franklin Institute, vol. 346, no 4, p. 328-348, mai 2009.
W. Y. Szeto, Y. Wu, et S. C. Ho, « An artificial bee colony algorithm for the capacitated vehicle routing problem », European Journal of Operational Research, vol. 215, no 1, p. 126-135, nov. 2011.
A. Brindle, « Genetic algorithms for function optimization », Doctoral Dissertation, University of Alberta. Edmonton, Canada, 1980.
Q.-K. Pan, L. Wang, J.-Q. Li, et J.-H. Duan, « A novel discrete artificial bee colony algorithm for the hybrid flowshop scheduling problem with makespan minimisation », Omega, vol. 45, p. 42-56, juin 2014.
DOI: https://doi.org/10.31449/inf.v44i4.3000
This work is licensed under a Creative Commons Attribution 3.0 License.