The electric vehicle routing problem with backhauls

Abstract: In the classical vehicle routing problem with backhauls (VRPB) the customers are divided into two sets; the linehaul and backhaul customers, so that the distribution and collection services of goods are separated into different routes. This is justified by the need to avoid the reorganization of the loads inside the vehicles, to reduce the return of the vehicles with empty load and to give greater priority to the customers of the linehaul. Many logistics companies have special responsibility to make their operations greener, and electric vehicles (EVs) can be an efficient solution. Thus, when the fleet consists of electric vehicles (EVs), the driving range is limited due to their battery capacities and, therefore, it is necessary to visit recharging stations along their route. In this paper the electric vehicle routing problem with backhauls (EVRPB) is introduced and formulated as a mixed integer linear programming model. This formulation is based on the generalization of the open vehicle routing problem considering a set of new constraints focussed on maintaining the arborescence condition of the linehaul and backhaul paths. Different charging points for the EVs are considered in order to recharge the battery at the end of the linehaul route or during the course of the backhaul route. Finally, a heuristic initialization methodology is proposed, in which an auxiliary graph is used for the efficient coding of feasible solutions to the problem. The operation and effectiveness of the proposed formulation is tested on two VRPB instance datasets of literature which have been adapted to the EVRPB.

How to cite this paper

 Granada-Echeverri, M., Cubides, L & Bustamante, J. (2020). The electric vehicle routing problem with backhauls.International Journal of Industrial Engineering Computations , 11(1), 131-152.

Refrences

Alinaghian, M., Kalantari, M. R., Bozorgi-Amiri, A., & Raad, N. G. (2016). A novel mathematical model for cross dock open-close vehicle routing problem with splitting. Int. J. Math. Sci. Comput.(IJMSC), 2(3), 21-31.
Arias, A., Granada, M., & Castro, C. A. (2017). Optimal probabilistic charging of electric vehicles in distribution systems. IET Electrical Systems in Transportation, 7(3), 246-251.
Bodin, L. (1983). Routing and scheduling of vehicles and crews, the state of the art. Comput. Oper. Res., 10(2), 63-211.
Cattaruzza, D., Absi, N., Feillet, D., & Vidal, T. (2014). A memetic algorithm for the multi trip vehicle routing problem. European Journal of Operational Research, 236(3), 833-848.
Chávez, J., Escobar, J., & Echeverri, M. (2016). A multi-objective Pareto ant colony algorithm for the Multi-Depot Vehicle Routing problem with Backhauls. International Journal of Industrial Engineering Computations, 7(1), 35-48.
Chávez, J., Escobar, J., Echeverri, M., & Meneses, C. (2018). A heuristic algorithm based on tabu search for vehicle routing problems with backhauls. Decision Science Letters, 7(2), 171-180.
Cormen, T. H., Leiserson, C. E., Rivest, R. L., & Stein, C. (2001). Introduction to algorithms second edition. The Knuth-Morris-Pratt Algorithm, year.
Dharmakeerthi, C. H., Mithulananthan, N., & Saha, T. K. (2012, July). Modeling and planning of EV fast charging station in power grid. In 2012 IEEE Power and Energy Society General Meeting (pp. 1-8). IEEE.
Electrification Coalition (2012) EV case study, the electric drive bellwether? - FedEx express on lessons learned - From global EV deployments. Tech. rep., Washington DC.
Fisher, M. L., Jaikumar, R., & Van Wassenhove, L. N. (1986). A multiplier adjustment method for the generalized assignment problem. Management Science, 32(9), 1095-1103.
Fourer, R., Gay, D. M., & Kernighan, B. W. (1990). A modeling language for mathematical programming. Management Science, 36(5), 519-554.
Ge, S., Feng, L., & Liu, H. (2011, September). The planning of electric vehicle charging station based on grid partition method. In 2011 International Conference on Electrical and Control Engineering (pp. 2726-2730). IEEE.
Goeke, D., & Schneider, M. (2015). Routing a mixed fleet of electric and conventional vehicles. European Journal of Operational Research, 245(1), 81-99.
Goetschalckx, M., & Jacobs-Blecha, C. (1989). The vehicle routing problem with backhauls. European Journal of Operational Research, 42(1), 39-51.
Irnich, S., Schneider, M., & Vigo, D. (2014). Chapter 9: Four Variants of the Vehicle Routing Problem. In Vehicle Routing: Problems, Methods, and Applications, Second Edition (pp. 241-271). Society for Industrial and Applied Mathematics.
Koç, Ç., & Laporte, G. (2018). Vehicle routing with backhauls: Review and research perspectives. Computers & Operations Research, 91, 79-91.
Letchford, A. N., Lysgaard, J., & Eglese, R. W. (2007). A branch-and-cut algorithm for the capacitated open vehicle routing problem. Journal of the Operational Research Society, 58(12), 1642-1651.
Li, F., Golden, B., & Wasil, E. (2007). The open vehicle routing problem: Algorithms, large-scale test problems, and computational results. Computers & Operations Research, 34(10), 2918-2930.
Liu, S., Lei, L., & Park, S. (2008). On the multi-product packing-delivery problem with a fixed route. Transportation Research Part E: Logistics and Transportation Review, 44(3), 350-360.
Liu, Z., Wen, F., & Ledwich, G. (2012). Optimal planning of electric-vehicle charging stations in distribution systems. IEEE Transactions on Power Delivery, 28(1), 102-110.
Lourenco, H. R., Martin, O. C., & Stuetzle, T. (2002). Handbook of Metaheuristics, chapter Iterated local search.
Mingozzi, A., Giorgi, S., & Baldacci, R. (1999). An exact method for the vehicle routing problem with backhauls. Transportation Science, 33(3), 315-329.
Ochi, L. S., Vianna, D. S., Drummond, L. M., & Victor, A. (1998). A parallel evolutionary algorithm for the vehicle routing problem with heterogeneous fleet. Future Generation Computer Systems, 14(5-6), 285-292.
Parragh, S. N., Doerner, K. F., & Hartl, R. F. (2008). A survey on pickup and delivery problems. Journal für Betriebswirtschaft, 58(1), 21-51.
Paz, J., Granada-Echeverri, M., & Escobar, J. (2018). The multi-depot electric vehicle location routing problem with time windows. International Journal of Industrial Engineering Computations, 9(1), 123-136.
Pessoa, A., De Aragão, M. P., & Uchoa, E. (2008). Robust branch-cut-and-price algorithms for vehicle routing problems. In The vehicle routing problem: Latest advances and new challenges (pp. 297-325). Springer, Boston, MA.
Pfriem, M., & Gauterin, F. (2013, November). Less range as a possible solution for the market success of electric vehicles in commercial fleets. In 2013 World Electric Vehicle Symposium and Exhibition (EVS27) (pp. 1-8). IEEE.
Prins, C. (2004). A simple and effective evolutionary algorithm for the vehicle routing problem. Computers & Operations Research, 31(12), 1985-2002.
Ropke, S., & Pisinger, D. (2006). A unified heuristic for a large class of vehicle routing problems with backhauls. European Journal of Operational Research, 171(3), 750-775.
Salari, M., Toth, P., & Tramontani, A. (2010). An ILP improvement procedure for the open vehicle routing problem. Computers & Operations Research, 37(12), 2106-2120.
Schrage, L. (1981). Formulation and structure of more complex/realistic routing and scheduling problems. Networks, 11(2), 229-232.
Stützle, T. (1999). Local search algorithms for combinatorial problems-analysis, algorithms and new applications. DISKI-Dissertationen zur Künstliken Intelligenz. In x, Sankt Augustin, Germany.
Taillard, É. (1993). Parallel iterative search methods for vehicle routing problems. Networks, 23(8), 661-673.
Toro, E. M., Franco, J. F., Echeverri, M. G., & Guimarães, F. G. (2017a). A multi-objective model for the green capacitated location-routing problem considering environmental impact. Computers & Industrial Engineering, 110, 114-125.
Toro, E., Franco, J., Echeverri, M., Guimarães, F., & Rendón, R. (2017b). Green open location-routing problem considering economic and environmental costs. International Journal of Industrial Engineering Computations, 8(2), 203-216.
Toth, P., & Vigo, D. (1997). An exact algorithm for the vehicle routing problem with backhauls. Transportation science, 31(4), 372-385.
Toth, P., & Vigo, D. (Eds.). (2002). The vehicle routing problem. Society for Industrial and Applied Mathematics.
Toth, P., & Vigo, D. (Eds.). (2014). Vehicle routing: problems, methods, and applications. Society for Industrial and Applied Mathematics.
Van Breedam, A. (1994). An Analysis of the Behavior of Heuristics for the Vehicle Routing Problem for a Selectrion of Problems with Vehicle-related, Customer-related, and Time-related Constraints. RUCA.
Vidal, T., Crainic, T. G., Gendreau, M., Lahrichi, N., & Rei, W. (2012). A hybrid genetic algorithm for multidepot and periodic vehicle routing problems. Operations Research, 60(3), 611-624.
Wade, A., & Salhi, S. (2003). An ant system algorithm for the mixed vehicle routing problem with backhauls. In Metaheuristics: computer decision-making (pp. 699-719). Springer, Boston, MA.
Wang, G., Xu, Z., Wen, F., & Wong, K. P. (2013). Traffic-constrained multiobjective planning of electric-vehicle charging stations. IEEE Transactions on Power Delivery, 28(4), 2363-2372.
Yang, J., & Sun, H. (2015). Battery swap station location-routing problem with capacitated electric vehicles. Computers & Operations Research, 55, 217-232.

Journals

IJIEC Volumes

Keywords

Authors

Countries

International Journal of Industrial Engineering Computations

The electric vehicle routing problem with backhauls Pages 131-152 Download PDF

Add Reviews