Comparing Two-Echelon and Single-Echelon Multi-Objective Capacitated Vehicle Routing Problems

Document Type : Research Paper

Authors

Department of Industrial Engineering, Shahed University, Tehran, Iran

Abstract

This paper aims to compare a two-echelon and a single-echelon distribution system. A mathematical model for the Single-Echelon Capacitated Vehicle Routing Problem (SE-CVRP) is proposed. This SE-CVRP is the counterpart of Two-Echelon Capacitated Vehicle Routing Problem (2E-CVRP) introduced in the authors’ previous work. The proposed mathematical model is Mixed-Integer Non-Linear Programming (MINLP) and minimizes 1) the total travel cost, 2) total waiting time of customers, and 3) total carbon dioxide emissions, simultaneously, in distributing perishable products. Applying some linearization methods changes the MINLP model into the Mixed Integer Linear Programming (MILP). In 2E-CVRP, shipments are delivered to customers by using intermediate depots named satellites while in SE-CVRP, direct shipments are used. Considering SE-CVRP, it was assumed that, by eliminating satellites, the large vehicles in depot were used for distribution. Because of the NP-hardness of the Vehicle Routing Problem (VRP) and its extensions, the NSGA-II algorithm was applied to solve the model. The objective functions of both distribution systems were compared in different size issues. The obtained results indicated that by considering large vehicles in an SE-CVRP, this distribution system would outperform the two-echelon one for all objectives of the small-size problems, the first two objectives of medium-size problems, and the first and third objectives of large-size problems.

Keywords

References

Angel-Bello, F., Martínez-Salazar, I. & Alvarez, A. (2013). Minimizing waiting times in a route design problem with multiple use of a single vehicle. Electronic Notes in Discrete Mathematics, 41, 269-276.
Baldacci, R., Mingozzi, A., Roberti, R., & Calvo, R. W. (2013). An exact algorithm for the two-echelon capacitated vehicle routing problem. Operations Research, 61(2), 298-314.
Beasley, J. E. (1990). OR-Library: distributing test problems by electronic mail. Journal of the operational research society, 41(11), 1069-1072.
Bektaş, T., & Laporte, G. (2011). The pollution-routing problem. Transportation Research Part B: Methodological, 45(8), 1232-1250.
Belgin, O., Karaoglan, I., & Altiparmak, F. (2013). Two-echelon vehicle routing problem with simultaneous pickup and delivery: Mathematical model and heuristic approach. Computers & Industrial Engineering, 115, 1-16.
Christofides, N., & Eilon, S. (1969). An algorithm for the vehicle-dispatching problem. Journal of the Operational Research Society, 20(3), 309-318.
Crainic, T. G., Perboli, G., Mancini, S., & Tadei, R. (2010). Two-echelon vehicle routing problem: a satellite location analysis. Procedia-Social and Behavioral Sciences, 2(3), 5944-5955.
Crainic, T. G., Mancini, S., Perboli, G., & Tadei, R. (2012). Impact of generalized travel costs on satellite location in the two-echelon vehicle routing problem. Procedia-Social and Behavioral Sciences, 39, 195-204.
Cuda, R., Guastaroba, G., & Speranza, M. G. (2015). A survey on two-echelon routing problems. Computers & Operations Research, 55, 185-199.
Dabia, S., Demir, E., & Van Woensel, T. (2014). An exact approach for the pollution-routing problem. Relatório técnico, Beta Research School for Operations Management and Logistics.
Dantzig, G. B., & Ramser, J. H. (1959). The truck dispatching problem. Management science, 6(1), 80-91.
Deb, K., Pratap, A., Agarwal, S., & Meyarivan, T. A. M. T. (2002). A fast and elitist multiobjective genetic algorithm: NSGA-II. IEEE transactions on evolutionary computation, 6(2), 182-197.
Eitzen, H., Lopez-Pires, F., Baran, B., Sandoya, F., & Chicaiza, J. L. (2017, September). A multi-objective two-echelon vehicle routing problem. An urban goods movement approach for smart city logistics. Computer Conference (CLEI), 2017 XLIII Latin American (pp. 1-10). IEEE.
Esmaili, M., & Sahraeian, R. (2017). A new Bi-objective model for a Two-echelon Capacitated Vehicle Routing Problem for Perishable Products with the Environmental Factor. International Journal of Engineering-Transactions A: Basics, 30(4), 523.
Fan, J. (2011). The vehicle routing problem with simultaneous pickup and delivery based on customer satisfaction. Procedia Engineering, 15, 5284-5289.
Feliu, J. G., Perboli, G., Tadei, R., & Vigo, D. (2007). The two-echelon capacitated vehicle routing problem. Technical report DEIS OR.INGCE 2007/2(R). Department of Electronics, Computer Science, and Systems: University of Bologna.
Glover, F., & Woolsey, E. (1974). Converting the 0-1 polynomial programming problem to a 0-1 linear program. Operations research, 22(1), 180-182.
Grangier, P., Gendreau, M., Lehuédé, F., & Rousseau, L. M. (2016). An adaptive large neighborhood search for the two-echelon multiple-trip vehicle routing problem with satellite synchronization. European Journal of Operational Research, 254(1), 80-91.
Hemmelmayr, V. C., Cordeau, J. F., & Crainic, T. G. (2012). An adaptive large neighborhood search heuristic for two-echelon vehicle routing problems arising in city logistics. Computers & operations research, 39(12), 3215-3228.
Holland, J. H. (1992). Adaptation in natural and artificial systems: an introductory analysis with applications to biology, control, and artificial intelligence. MIT press.
Jepsen, M., Spoorendonk, S., & Ropke, S. (2013). A branch-and-cut algorithm for the symmetric two-echelon capacitated vehicle routing problem. Transportation Science, 47(1), 23-37.
Perboli, G., & Tadei, R. (2010). New families of valid inequalities for the two-echelon vehicle routing problem. Electronic notes in discrete mathematics, 36, 639-646.
Perboli, G., Tadei, R., & Vigo, D. (2011). The two-echelon capacitated vehicle routing problem: models and math-based heuristics. Transportation Science, 45(3), 364-380.
Sadegheih, A., Drake, P. R., Li, D., & Sribenjachot, S. (2011). Global supply chain management under the carbon emission trading program using mixed integer programming and genetic algorithm.
Sahraeian, R., & Esmaeili, M. (2018). A multi-objective Two-Echelon Capacitated Vehicle Routing Problem for perishable products. Journal of Industrial and Systems Engineering, 11(2).
Sitek, P., & Wikarek, J. (2014). A novel integrated approach to the modelling and solving of the Two-Echelon Capacitated Vehicle Routing Problem. Production & Manufacturing Research, 2(1), 326-340.
Song, L., Gu, H., & Huang, H. (2017). A lower bound for the adaptive two-echelon capacitated vehicle routing problem. Journal of Combinatorial Optimization, 33(4), 1145-1167.
Toth, P., & Vigo, D. (2002). The vehicle routing problem, ser. SIAM monographs on discrete mathematics and applications. Society for Industrial and Applied Mathematics.
Journal of Quality Engineering and Production Optimization
Volume 4, Issue 1
June 2019
Pages 1-16

Files

Share

How to cite

Statistics