An Adaptive Large Neighborhood Search Heuristic for the Green Vehicle Routing Problem with Simultaneously Pickup and Delivery and Hard Time Windows

Document Type : Research Paper

Authors

1 Iran University of Science & Technology

2 Iran University of Science and Technology

Abstract

The classical models of vehicle routing generally focused on minimizing total distance and travel time, however in green vehicle routing problem the main objective is minimizing total emissions and fuel consumption besides the other objects.
In this paper, extension of GVRP with minimizing fuel and emission costs presented that considered pickup and delivery constraints with hard time windows. Travel time in this model is not constant and speed of vehicles would be determined in regards to customers’ time widows. In this paper, a heuristic based adaptive large neighborhood search proposed for solving the model. Construction algorithm in this method is heuristic based algorithm with proposed criterion according to pick up and delivery constrains and time windows with assumption of variable speed. Computational results confirms efficiency of this algorithm.

Keywords

Main Subjects


[1]       Salimifard, K., Shahbandarzadeh, H.,  Raeesi, R. (2012). Green transportation and the role of operation research, international conference on traffic and transportation engineering.
[2]       Palmer, A. (2007). The development of an integrated routing and carbon dioxide emissions model for goods vehicles, PhD thesis. Bedford, United Kingdom:Cranfield University.
[3]       Kara et al. (2007). Energy minimizing vehicle routing problem, Combinatorial optimization and applications, 4616: 62-71.
[4]       Maden, W., Eglese, R.W., Black, D. (2010). Vehicle routing and scheduling with time varying data: a case study, Journal of the Operational Research Society, 61: 515-522.
[5]       Ubeda, S., Arcelus, F. J., Faulin, J. (2011). Green logistics at Eroski: A case study, International Journal of Production Economics, 131(1): 44–51.
[6]       Suzuki, Y. (2011). A new truck-routing approach for reducing fuel consumption and pollutants emission, Transportation Research Part D: Transport and Environment, 16(1): 73–77.
[7]       Bektaş, T., Laporte, G. (2011). pollution routing problem, Transportation Research Part B, 45(8): 1232–1250.
[8]       Faulin, J., Juan, A., Lera, F., Grasman, S. (2011). Solving the capacitated vehicle routing problem with environmental criteria based on real estimations in road transportation: a case study", Procedia – Social and Behavioral Sciences, 20: 323–334.
[9]       Xiao, Y., Zhao, Q., Kaku, I., Xu, Y. (2012). "Development of a fuel consumption optimization model for the capacitated vehicle routing problem", Computers & Operations Research, 39(7): 1419–1431.
[10]   Erdoğan, S.,  Miller-Hooks, E. (2012). A green vehicle routing problem, Transportation Research Part E: Logistics and Transportation Review, 48: 100–114.
[11]   Demir, E., Laporte, G. (2012). An adaptive large neighborhood search heuristic for the Pollution-Routing Problem. European Journal of Operational Research, 223: 346–359.
[12]   Ramos, T., Oliveira, R. (2011). Delimitation of service areas in reverse logistics networks with multiple depots, Journal of the Operational Research Society, 62: 1198–1210.
[13]   Taha, M., Fors, M. N., Shoukry, A. A. (2014). An Exact Solution for a Class of Green Vehicle Routing Problem, in International Conference on Industrial Engineering and Operations Management.
[14]   Kopfer, H. W., Schönberger, J., Kopfer, H. (2013). Emissions Minimization Vehicle Routing Problem in Dependence of Different Vehicle Classes,  Dynamics in Logistics: 49-58.
[15]   Demir, E., Bektaş, T., Laporte, G. (2014). The bi-objective Pollution-Routing Problem, European Journal of Operational Research, 232: 464–478.
[16]   Çatay, B. (2010). A new saving-based ant algorithm for the Vehicle Routing Problem with Simultaneous Pickup and Delivery, Expert Systems with Applications , 10(37): 6809-6817.
[17]   Fan, J. (2011). The Vehicle Routing Problem with Simultaneous Pickup and Delivery Based on Customer Satisfaction, Procedia Engineering, 15: 5284-5289.
[18]   Petersen, H. L., Ropke, S. (2011). The pickup and delivery problem with cross-docking opportunity, Computational Logistics Springer Berlin Heidelberg: 101-113.
[19]   Coelho, I. M. Munhoz, P.L.A. Haddad, M.N., Souza, M.J.F. Ochi, L.S. (2012). A hybrid heuristic based on General Variable Neighborhood Search for the Single Vehicle Routing Problem with Deliveries and Selective Pickups, Electronic Notes in Discrete Mathematics, 39: 99-106.
[20]   Wang, C. Qiu, Y. (2012). Vehicle Routing Problem with Stochastic Demands and Simultaneous Delivery and Pickup Based on the Cross-Entropy Method, Advances in Automation and Robotics, Springer Berlin Heidelberg, 2: 55-60.
[21]   Wang, H. F. Chen, Y. Y. (2012). A genetic algorithm for the simultaneous delivery and pickup problems with time window, Computers & Industrial Engineering, 62(1): 84–95.
[22]  ستاک مصطفی، عزیزی وحید، کریمی حسین (1393). مساله مکان یابی و مسیریابی چنددپویی ظرفیت دار با برداشت و تحویل همزمان و بارهای برش یافته: مدلسازی و حل ابتکاری، نشریه پژوهش‌های مهندسی صنایع در سیستم‌های تولید، شماره 4: 67-81.
[23]   Barth, M., Younglove, T., Scora, G. (2005). Development of a heavy-duty diesel modal emissions and fuel consumption model, California PATH Research Report.
[24]   Shaw, P. (1998). Using constraint programming and local search methods to solve vehicle routing problems, in Proceedings of the 4th International Conference on Principles and Practice of Constraint Programming., New York.
[25]   Pisinger, D.R.S. (2007). A General Heuristic for Vehicle Routing Problems, Computers & Operations Research, 34(8): 2403–2435.
[26]   Dethloff, J. (2001). Vehicle routing and reverse logistics: the vehicle routing problem with simultaneous delivery and pick-up, OR Spektrum,  23: 79-96.