Published September 26, 2020
| Version v1
Publication
Open
Stochastic multi-depot vehicle routing problem with pickup and delivery: an ILS approach
Creators
- 1. Institute for Systems and Computer Engineering of Porto
- 2. Universidade Estadual de Campinas (UNICAMP)
- 3. Universidade do Porto
Description
We present a natural probabilistic variation of the multi-depot vehicle routing problem with pickup and delivery (MDVRPPD).In this paper, we present a variation of this deterministic problem, where each pair of pickup and delivery points are present with some probability, and their realization are only known after the routes are computed.We denote this stochastic version by S-MDVRPPD.One route for each depot must be computed satisfying precedence constraints, where each pickup point must appear before its delivery pair in the route.The objective is to find a solution with minimum expected traveling distance.We present a closed-form expression to compute the expected length of an a priori route under general probabilistic assumptions.To solve the S-MDVRPPD we propose an Iterated Local Search (ILS) that uses the Variable Neighborhood Descent (VND) as local search procedure.The proposed heuristic was compared with a Tabu Search (TS) algorithm based on a previous work.We evaluate the performance of these heuristics on a data set adapted from TSPLIB instances.The results show that the ILS proposed is efficient and effective to solve S-MDVRPPD.
Translated Descriptions
⚠️
This is an automatic machine translation with an accuracy of 90-95%
Translated Description (Arabic)
نقدم تباينًا احتماليًا طبيعيًا لمشكلة توجيه المركبات متعددة المستودعات مع الاستلام والتسليم (MDVRPPD). في هذه الورقة، نقدم تباينًا لهذه المشكلة الحتمية، حيث يوجد كل زوج من نقاط الاستلام والتسليم مع بعض الاحتمالات، ولا يُعرف تحقيقها إلا بعد حساب المسارات. نشير إلى هذه النسخة العشوائية بواسطة S - MDVRPPD. يجب حساب مسار واحد لكل مستودع يرضي قيود الأسبقية، حيث يجب أن تظهر كل نقطة التقاء قبل زوج التسليم الخاص بها في الطريق. الهدف هو إيجاد حل مع الحد الأدنى من مسافة السفر المتوقعة. نقدم تعبيرًا مغلقًا لحساب الطول المتوقع لطريق مسبق بموجب افتراضات احتمالية عامة. لحل S - MDVRPPD نقترح بحثًا محليًا متكررًا (ILS) يستخدم النسب المتغير للجوار (VND) كإجراء بحث محلي. تمت مقارنة الاستدلال المقترح مع خوارزمية بحث الطابو (TS) بناءً على عمل سابق. نقوم بتقييم أداء هذه الاستدلالات على مجموعة بيانات مقتبسة من مثيلات TSPLIB. تظهر النتائج أن ILS المقترح فعال وفعال لحل S - MDVRPPD.Translated Description (French)
Nous présentons une variation probabiliste naturelle du problème de routage des véhicules multi-dépôts avec ramassage et livraison (MDVRPPD).Dans cet article, nous présentons une variation de ce problème déterministe, où chaque paire de points de ramassage et de livraison sont présents avec une certaine probabilité, et leur réalisation n'est connue qu'après le calcul des itinéraires.Nous désignons cette version stochastique par S-MDVRPPD.Un itinéraire pour chaque dépôt doit être calculé en satisfaisant aux contraintes de priorité, où chaque point de ramassage doit apparaître avant sa paire de livraison dans l'itinéraire. L'objectif est de trouver une solution avec une distance de déplacement minimale attendue. Nous présentons une expression de forme fermée pour calculer la longueur attendue d'un itinéraire a priori sous des hypothèses probabilistes générales. Pour résoudre le S-MDVRPPD, nous proposons une recherche locale itérée (ils) qui utilise la descente de quartier variable (VND) comme procédure de recherche locale. L'heuristique proposée a été comparée à un algorithme de recherche Tabu (TS) basé sur un travail précédent. Nous évaluons la performance de ces heuristiques sur un ensemble de données adapté des instances TSPLIB. Les résultats montrent que l'ils proposé est efficace et efficient pour résoudre le S-MDVRPPD.Translated Description (Spanish)
Presentamos una variación probabilística natural del problema de enrutamiento de vehículos multidepósito con recogida y entrega (MDVRPPD). En este documento, presentamos una variación de este problema determinista, donde cada par de puntos de recogida y entrega están presentes con cierta probabilidad, y su realización solo se conoce después de que se calculan las rutas. Denotamos esta versión estocástica por S-MDVRPPD.Una ruta para cada depósito debe calcularse satisfaciendo las restricciones de precedencia, donde cada punto de recogida debe aparecer antes de su par de entrega en la ruta. El objetivo es encontrar una solución con la distancia de viaje mínima esperada. Presentamos una expresión de forma cerrada para calcular la longitud esperada de una ruta a priori bajo supuestos probabilísticos generales. Para resolver el S-MDVRPPD, proponemos una Búsqueda local iterada (ILS) que utiliza el Descenso de vecindario variable (VND) como procedimiento de búsqueda local. La heurística propuesta se comparó con un algoritmo de Búsqueda tabú (TS) basado en un trabajo anterior. Evaluamos el rendimiento de estas heurísticas en un conjunto de datos adaptado de instancias TSPLIB. Los resultados muestran que el ILS propuesto es eficiente y efectivo para resolver el S-MDVRPPD.Files
127.pdf.pdf
Files
(202.8 kB)
| Name | Size | Download all |
|---|---|---|
|
md5:c836f64b6ec1182362acac915fc1cd9f
|
202.8 kB | Preview Download |
Additional details
Additional titles
- Translated title (Arabic)
- مشكلة عشوائية في توجيه المركبات متعددة المستودعات مع الاستلام والتسليم: نهج ILS
- Translated title (French)
- Problème stochastique d'acheminement des véhicules multi-dépôts avec ramassage et livraison : une approche ils
- Translated title (Spanish)
- Problema estocástico de enrutamiento de vehículos multidepósito con la recogida y la entrega: un enfoque ILS
Identifiers
- Other
- https://openalex.org/W3092160800
- DOI
- 10.15439/2020f127
References
- https://openalex.org/W1969886247
- https://openalex.org/W1972075556
- https://openalex.org/W1984143531
- https://openalex.org/W2010334716
- https://openalex.org/W2017641951
- https://openalex.org/W2047612779
- https://openalex.org/W2050819731
- https://openalex.org/W2051911912
- https://openalex.org/W2084151425
- https://openalex.org/W2112686410
- https://openalex.org/W2114217004
- https://openalex.org/W2167890839
- https://openalex.org/W2547671150
- https://openalex.org/W2623014010
- https://openalex.org/W2728990861
- https://openalex.org/W2782547848
- https://openalex.org/W2811315814
- https://openalex.org/W2975218764
- https://openalex.org/W3003557778
- https://openalex.org/W4244421641