The capacitated vehicle routing problem with soft time windows and stochastic travel times

Main Article Content

Autores

Jorge Oyola, Ph. D. http://orcid.org/0000-0002-6501-7036

Abstract

A full multiobjective approach is employed in this paper to deal with a stochastic multiobjective capacitated vehicle routing problem (CVRP). In this version of the problem, the demand is considered to be deterministic, but the travel times are assumed to be stochastic. A soft time window is tied to every customer and there is a penalty for starting the service outside the time window. Two objectives are minimized, the total length and the time window penalty. The suggested solution method includes a non-dominated sorting genetic algorithm (NSGA) together with a variable neighborhood search (VNS) heuristic. It was tested on instances from the literature and compared to a previous solution approach. The suggested method is able to find solutions that dominate some of the previously best known stochastic multiobjective CVRP solutions.

Keywords:

Article Details

Licence

Creative Commons License

This work is licensed under a Creative Commons Attribution 4.0 International License.

All articles included in the Revista Facultad de Ingeniería are published under the Creative Commons (BY) license.

Authors must complete, sign, and submit the Review and Publication Authorization Form of the manuscript provided by the Journal; this form should contain all the originality and copyright information of the manuscript.

The authors who publish in this Journal accept the following conditions:

a. The authors retain the copyright and transfer the right of the first publication to the journal, with the work registered under the Creative Commons attribution license, which allows third parties to use what is published as long as they mention the authorship of the work and the first publication in this Journal.

b. Authors can make other independent and additional contractual agreements for the non-exclusive distribution of the version of the article published in this journal (eg, include it in an institutional repository or publish it in a book) provided they clearly indicate that the work It was first published in this Journal.

c. Authors are allowed and recommended to publish their work on the Internet (for example on institutional or personal pages) before and during the process.
review and publication, as it can lead to productive exchanges and a greater and faster dissemination of published work.

d. The Journal authorizes the total or partial reproduction of the content of the publication, as long as the source is cited, that is, the name of the Journal, name of the author (s), year, volume, publication number and pages of the article.

e. The ideas and statements issued by the authors are their responsibility and in no case bind the Journal.

References

[1] G. B. Dantzig, and J. H. Ramser, "The truck dispatching problem," Management Science, vol. 6 (1), pp. 80-91, 1959. DOI: https://doi.org/10.1287/mnsc.6.1.80.

[2] P. Toth, and D. Vigo, "Models, relaxations and exact approaches for the capacitated vehicle routing problem," Discrete Applied Mathematics, vol. 123 (1-3), pp. 487–512, 2002. DOI: https://doi.org/10.1016/S0166-218X(01)00351-1.

[3] M. Gendreau, G. Laporte, and R. Seguin, "Stochastic vehicle routing," European Journal of Operational Research, vol. 88 (1), pp. 3-12, Jan. 1996. DOI: https://doi.org/10.1016/0377-2217(95)00050-X.

[4] J. Oyola, H. Arntzen, and D. L. Woodruff, "The stochastic vehicle routing problem, a literature review, part I: models," EURO Journal on Transportation and Logistics, vol. 7 (3), p. 193–221, Sep. 2018. DOI: https://doi.org/10.1007/s13676-016-0100-5.

[5] R. A. Russell, and T. L. Urban, "Vehicle routing with soft time windows and Erlang travel times," Journal of the Operational Research Society, vol. 59 (9), pp. 1220-1228, Sep. 2008. DOI: https://doi.org/10.1057/palgrave.jors.2602465.

[6] J. Current, and H. Min, "Multiobjective design of transportation networks: Taxonomy and annotation," European Journal of Operational Research, vol. 26 (2), pp. 187-201, Aug. 1986. DOI: https://doi.org/10.1016/0377-2217(86)90180-3.

[7] Y. Collette, and P. Siarry, Multiobjective optimization: principles and case studies, Berlin: Springer, 2003.

[8] N. Jozefowiez, F. Semet, and E. Talbi, "Target aiming pareto search and its application to the vehicle routing problem with route balancing," Journal of Heuristics, vol. 13 (5), pp. 455-469, Sep. 2007. DOI: https://doi.org/10.1007/s10732-007-9022-6.

[9] R. Caballero, E. Cerdá, M. D. M. Muñoz, and L. Rey, "Stochastic approach versus multiobjective approach for obtaining efficient solutions in stochastic multiobjective programming problems," European Journal of Operational Research, vol. 158 (3), pp. 633-648, Nov. 2004. DOI: https://doi.org/10.1016/S0377-2217(03)00371-0.

[10] X. Li, P. Tian, and S. C. Leung, "Vehicle routing problems with time windows and stochastic travel and service times: Models and algorithm," International Journal of Production Economics, vol. 125 (1), pp. 137-145, May. 2010. DOI: https://doi.org/10.1016/j.ijpe.2010.01.013.

[11] H. Lei, G. Laporte, and B. Guo, "A generalized variable neighborhood search heuristic for the capacitated vehicle routing problem with stochastic service times," TOP, vol. 20 (1), pp. 99 - 118, Apr. 2012. DOI: https://doi.org/10.1007/s11750-011-0188-6.

[12] T. Zhang, W. Chaovalitwongse, and Y. Zhang, "Scatter search for the stochastic travel-time vehicle routing problem with simultaneous pick-ups and deliveries," Computers & Operations Research, vol. 39 (10), pp. 2277-2290, Oct. 2012. DOI: https://doi.org/10.1016/j.cor.2011.11.021.

[13] D. Taş, N. Dellaert, T. Van Woensel, and T. de Kok, "Vehicle routing problem with stochastic travel times including soft time windows and service costs," Computers & Operations Research, vol. 40 (1), pp. 214-224, Jan. 2013. DOI: https://doi.org/10.1016/j.cor.2012.06.008.

[14] D. Taş, M. Gendreau, N. Dellaert, T. Van Woensel, and A. de Kok, "Vehicle routing with soft time windows and stochastic travel times: A column generation and branch-and-price solution approach," European Journal of Operational Research, vol. 236 (3), pp. 789-799, Aug. 2014. DOI: https://doi.org/10.1016/j.ejor.2013.05.024.

[15] A. S. Kenyon, and D. P. Morton, "Stochastic vehicle routing with random travel times," Transportation Science, vol. 37 (1), pp. 69-82, Feb. 2003. DOI: https://doi.org/10.1287/trsc.37.1.69.12820.

[16] C. Lee, K. Lee, and S. Park, "Robust vehicle routing problem with deadlines and travel time/demand uncertainty," Journal of the Operational Research Society, vol. 63 (9), pp. 1294-1306, Sep. 2012. DOI: https://doi.org/10.1057/jors.2011.136.

[17] M. Gendreau, O. Jabali, and W. Rei, "Stochastic vehicle routing problems.," in Vehicle Routing: Problems, Methods, and Applications, Philadelphia, Society for Industrial and Applied Mathematics, Nov. 2014, pp. 213-239. DOI: https://doi.org/10.1137/1.9781611973594.ch8.

[18] J. Oyola, H. Arntzen, and D. L. Woodruff, "The stochastic vehicle routing problem, a literature review, part II: solution methods," EURO Journal on Transportation and Logistics, vol. 6 (4), p. 349–388, Dec. 2017. DOI: https://doi.org/10.1007/s13676-016-0099-7.

[19] A. Ahmadi-Javid, and A. H. Seddighi, "A location-routing problem with disruption risk," Transportation Research Part E Logistics and Transportation Review, vol. 53, pp. 63-82, Jul. 2013. DOI: https://doi.org/10.1016/j.tre.2013.02.002.

[20] A. Juan, J. Faulin, S. Grasman, D. Riera, J. Marull, and C. Mendez, "Using safety stocks and simulation to solve the vehicle routing problem with stochastic demands," Transportation Research Part C Emerging Technologies, vol. 19 (5), pp. 751-765, Aug. 2011. DOI: https://doi.org/10.1016/j.trc.2010.09.007.

[21] K. Tan, C. Cheong, and C. Goh, "Solving multiobjective vehicle routing problem with stochastic demand via evolutionary computation," European Journal of Operational Research, vol. 177 (2), pp. 813-839, Mar. 2007. DOI: https://doi.org/10.1016/j.ejor.2005.12.029.

[22] N. Jozefowiez, F. Semet, and E. Talbi, "An evolutionary algorithm for the vehicle routing problem with route balancing," European Journal of Operational Research, vol. 195 (3), pp. 761-769, Jun. 2009. DOI: https://doi.org/10.1016/j.ejor.2007.06.065.

[23] J. E. Mendoza, B. Castanier, C. Gueret, A. L. Medaglia, and N. Velasco, "A memetic algorithm for the multi-compartment vehicle routing problem with stochastic demands," Computers & Operations Research, vol. 37 (11), pp. 1886-1898, Nov. 2010. DOI: https://doi.org/10.1016/j.cor.2009.06.015.

[24] K. Sörensen, and M. Sevaux, "A practical approach for robust and flexible vehicle routing using metaheuristics and Monte Carlo sampling," Journal of Mathematical Modelling and Algorithms, vol. 8 (4), pp. 387-407, Dec. 2009. DOI: https://doi.org/10.1007/s10852-009-9113-5.

[25] K. Deb, A. Pratap, S. Agarwal, and T. Meyarivan, "A fast and elitist multiobjective genetic algorithm: NSGA-II," IEEE Trans. Evol. Comp, vol. 6 (2), pp. 182-197, Apr. 2002. DOI: https://doi.org/10.1109/4235.996017.

[26] C. Prins, "A simple and effective evolutionary algorithm for the vehicle routing problem," Computers & Operations Research, vol. 31 (12), pp. 1985-2002, Oct. 2004. DOI: https://doi.org/10.1016/S0305-0548(03)00158-8.

[27] W.-C. Chiang, and R. A. Russell, "A metaheuristic for the vehicle-routeing problem with soft time windows," Journal of the Operational Research Society, vol. 55 (12), pp. 1298-1310, Dec. 2004. DOI: https://doi.org/10.1057/palgrave.jors.2601791.

[28] M. M. Solomon, "Algorithms for the vehicle routing and scheduling problems with time window constraints," Operations Research, vol. 35 (2), pp. 254-265, 1987. DOI: https://doi.org/10.1287/opre.35.2.254.

[29] J.-Y. Potvin, and S. Bengio, "The vehicle routing problem with time windows part II: Genetic search," INFORMS Journal on Computing, vol. 8 (2), pp. 165-172, May. 1996. DOI: https://doi.org/10.1287/ijoc.8.2.165.

[30] P. Venkataraman, Applied Optimization with MATLAB Programming, Hoboken: John Wiley & Sons Inc., 2009.

[31] J. Mendoza, L.-M. Rousseau, and J. Villegas, "A hybrid metaheuristic for the vehicle routing problem with stochastic demand and duration constraints," Journal of Heuristics, vol. 22 (4), p. 539–566, Aug. 2016. DOI: https://doi.org/10.1007/s10732-015-9281-6.

[32] M. Kaut, and S. W. Wallace, "Evaluation of scenario-generation methods for stochastic programming," Pacific Journal of Optimization, vol. 3 (2), pp. 257-271, 2007.

[33] J. D. Knowles, "Local-search and hybrid evolutionary algorithms for Pareto optimization," Ph. D. Dissertation, University of Reading, Reading, 2002.

[34] P. Mateo, and I. Alberto, "A mutation operator based on a pareto ranking for multi-objective evolutionary algorithms," Journal of Heuristics, vol. 18 (1), pp. 53-89, Feb. 2012. DOI: https://doi.org/10.1007/s10732-011-9156-4.

Downloads

Download data is not yet available.