The capacitated vehicle routing problem with soft time windows and stochastic travel times
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...
| Main Author: | |
|---|---|
| Format: | Online |
| Language: | eng |
| Published: |
Universidad Pedagógica y Tecnológica de Colombia
2019
|
| Subjects: | |
| Online Access: | https://revistas.uptc.edu.co/index.php/ingenieria/article/view/8782 |
| _version_ | 1801706094901329920 |
|---|---|
| author | Oyola, Jorge |
| author_facet | Oyola, Jorge |
| author_sort | Oyola, Jorge |
| collection | OJS |
| description | 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. |
| format | Online |
| id | oai:oai.revistas.uptc.edu.co:article-8782 |
| institution | Revista Facultad de Ingeniería |
| language | eng |
| publishDate | 2019 |
| publisher | Universidad Pedagógica y Tecnológica de Colombia |
| record_format | ojs |
| spelling | oai:oai.revistas.uptc.edu.co:article-87822021-07-13T02:26:32Z The capacitated vehicle routing problem with soft time windows and stochastic travel times El problema de enrutamiento de vehículos con ventanas de tiempo suave y tiempos de viaje estocásticos Oyola, Jorge genetic algorithms heuristic algorithms multiobjective programming random processes vehicle routing algoritmos genéticos algoritmos heurísticos optimización multiobjetivo proceso aleatorio ruteo de vehículos 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. Un enfoque totalmente multiobjetivo es usado en este artículo para estudiar un problema de enrutamiento de vehículos capacitado (CVRP), estocástico y multiobjetivo. En esta versión del problema, la demanda se considera determinística, pero los tiempos de viaje son asumidos como estocásticos. Una ventana de tiempo suave es asociada con cada cliente y hay una penalización por iniciar el servicio por fuera de esta. Dos objetivos son minimizados, la distancia total recorrida y la penalización por no cumplir con la ventana de tiempo. El método de solución propuesto incluye un algoritmo genético con ordenamiento no dominado (NSGA) y una heurística de búsqueda de vecindad variable (VNS). Se probó en problemas de la literatura y se comparó con un enfoque previo de solución. El método propuesto es capaz de encontrar soluciones que dominan algunas de las mejores soluciones conocidas para el CVRP multiobjetivo. Universidad Pedagógica y Tecnológica de Colombia 2019-01-10 info:eu-repo/semantics/article info:eu-repo/semantics/publishedVersion research investigación application/pdf application/xml https://revistas.uptc.edu.co/index.php/ingenieria/article/view/8782 10.19053/01211129.v28.n50.2019.8782 Revista Facultad de Ingeniería; Vol. 28 No. 50 (2019); 19-33 Revista Facultad de Ingeniería; Vol. 28 Núm. 50 (2019); 19-33 2357-5328 0121-1129 eng https://revistas.uptc.edu.co/index.php/ingenieria/article/view/8782/7284 https://revistas.uptc.edu.co/index.php/ingenieria/article/view/8782/7501 https://revistas.uptc.edu.co/index.php/ingenieria/article/view/8782/7530 N.A. N.A. |
| spellingShingle | genetic algorithms heuristic algorithms multiobjective programming random processes vehicle routing algoritmos genéticos algoritmos heurísticos optimización multiobjetivo proceso aleatorio ruteo de vehículos Oyola, Jorge The capacitated vehicle routing problem with soft time windows and stochastic travel times |
| title | The capacitated vehicle routing problem with soft time windows and stochastic travel times |
| title_alt | El problema de enrutamiento de vehículos con ventanas de tiempo suave y tiempos de viaje estocásticos |
| title_full | The capacitated vehicle routing problem with soft time windows and stochastic travel times |
| title_fullStr | The capacitated vehicle routing problem with soft time windows and stochastic travel times |
| title_full_unstemmed | The capacitated vehicle routing problem with soft time windows and stochastic travel times |
| title_short | The capacitated vehicle routing problem with soft time windows and stochastic travel times |
| title_sort | capacitated vehicle routing problem with soft time windows and stochastic travel times |
| topic | genetic algorithms heuristic algorithms multiobjective programming random processes vehicle routing algoritmos genéticos algoritmos heurísticos optimización multiobjetivo proceso aleatorio ruteo de vehículos |
| topic_facet | genetic algorithms heuristic algorithms multiobjective programming random processes vehicle routing algoritmos genéticos algoritmos heurísticos optimización multiobjetivo proceso aleatorio ruteo de vehículos |
| url | https://revistas.uptc.edu.co/index.php/ingenieria/article/view/8782 |
| work_keys_str_mv | AT oyolajorge thecapacitatedvehicleroutingproblemwithsofttimewindowsandstochastictraveltimes AT oyolajorge elproblemadeenrutamientodevehiculosconventanasdetiemposuaveytiemposdeviajeestocasticos AT oyolajorge capacitatedvehicleroutingproblemwithsofttimewindowsandstochastictraveltimes |
