nach oben

Pattern Recognition and Image Analysis

Erschienen in:

01.06.2023 | SELECTED CONFERENCE PAPERS

Deep Reinforcement Learning for the Capacitated Pickup and Delivery Problem with Time Windows

verfasst von: A. G. Soroka, A. V. Meshcheryakov, S. V. Gerasimov

Erschienen in: Pattern Recognition and Image Analysis | Ausgabe 2/2023

Einloggen

Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.

search-config

KI-gestützte Suche

Aus

Abstract

The vehicle routing problem with pickup and delivery is one of the most important problems in the context of global urban population growth. Although these kinds of small-size problems can be solved using various classical approaches, a fast (or real-time) route optimizer under real-world constraints (such as throughput and time window constraints) for medium- and large-size problems is still a challenge. In this work, we first successfully applied a deep reinforcement learning approach (a modified JAMPR model) to solve the capacitated pickup and delivery problem with time windows (CPDPTW). We obtained a robust model that gives a fast optimal solution for small- to medium-size problems and gives a fast suboptimal solution for large-size (>200) problems.

Vorheriger Artikel Cross-Correlation Methods in Problem of Search and Identification of Transient Objects in Astronomical Images

Nächster Artikel Image Neural Network Classifier by Detail Attributes

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

über 102.000 Bücher
über 537 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Finance + Banking
Management + Führung
Marketing + Vertrieb
Maschinenbau + Werkstoffe
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 340 Zeitschriften

aus folgenden Fachgebieten:

Bauwesen + Immobilien
Business IT + Informatik
Finance + Banking
Management + Führung
Marketing + Vertrieb
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 390 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Maschinenbau + Werkstoffe

Jetzt Wissensvorsprung sichern!

Jetzt informieren

B. Balaji, J. Bell-Masterson, E. Bilgin, A. Damianou, P. M. Garcia, A. Jain, R. Luo, A. Maggiar, B. Narayanaswamy, and Ch. Ye, “ORL: Reinforcement learning benchmarks for online stochastic optimization problems,” (2019). arXiv:1911.10641 [cs.LG]

K. Braekers, K. Ramaekers, I. Van Nieuwenhuyse, “The vehicle routing problem: State of the art classification and review,” Comput. Ind. Eng. 99, 300–313 (2016). https://doi.org/10.1016/j.cie.2015.12.007CrossRef

O. Bräysy and M. Gendreau, “Vehicle routing problem with time windows, Part I: Route construction and local search algorithms,” Transp. Sci. 39, 104–118 (2005). https://doi.org/10.1287/trsc.1030.0056CrossRef

X. Chen and Yu. Tian, “Learning to perform local rewriting for combinatorial optimization,” Adv. Neural Inf. Process. Syst. 32 (2019).

G. Clarke and J. W. Wright, “Scheduling of vehicles from a central depot to a number of delivery points,” Oper. Res. 12, 568–581 (1964). https://doi.org/10.1287/opre.12.4.568CrossRef

G. Dantzig, R. Fulkerson, and S. Johnson, “Solution of a large-scale traveling-salesman problem,” J. Oper. Res. Soc. Am. 2, 393–410 (1954). https://doi.org/10.1007/978-3-540-68279-0_1MathSciNetCrossRefMATH

G. B. Dantzig and J. H. Ramser, “The truck dispatching problem,” Manage. Sci. 6, 80–91 (1959). https://doi.org/10.1287/mnsc.6.1.80MathSciNetCrossRefMATH

J. K. Falkner and L. Schmidt-Thieme, “Learning to solve vehicle routing problems with time windows through joint attention,” (2020). arXiv:2006.09100 [cs.LG]

W. Kool, H. Van Hoof, and M. Welling, “Attention, learn to solve routing problems!,” (2018). arXiv:1803.08475 [stat.ML]

10.

S. Li, Zh. Yan, and C. Wu, “Learning to delegate for large-scale vehicle routing,” Adv. Neural Inf. Process. Syst. 34 (2021). https://doi.org/10.48550/arXiv.2107.04139

11.

S. Lin and B. W. Kernighan, “An effective heuristic algorithm for the traveling-salesman problem,” Oper. Res. 21, 498–516 (1973). https://doi.org/10.1287/opre.21.2.498MathSciNetCrossRefMATH

12.

J. D. Little, K. G. Murty, D. W. Sweeney, and C. Karel, “An algorithm for the traveling salesman problem,” Oper. Res. 11, 972–989 (1963). https://doi.org/10.1287/opre.11.6.972CrossRefMATH

13.

H. Lu, X. Zhang, and Sh. Yang, “A learning-based iterative method for solving vehicle routing problems,” in Int. Conf. on Learning Representations (2019).

14.

M. Nazari, A. Oroojlooy, L. Snyder, and M. Takác, “Reinforcement learning for solving the vehicle routing problem,” Adv. Neural Inf. Process. Syst. 31 (2018). https://doi.org/10.48550/arXiv.1802.04240

15.

I. Or, “Traveling salesman type combinatorial problems and their relation to the logistics of regional blood banking,” PhD Thesis (Northwestern Univ., 1976)

16.

S. N. Parragh, K. F. Doerner, and R. F. Hartl, “A survey on pickup and delivery problems,” J. Betriebswirtschaft 58 (1), 21–51 (2008). https://doi.org/10.1007/s11301-008-0033-7CrossRef

17.

L. Perron, “Operations research and constraint programming at Google,” in Principles and Practice of Constraint Programming—CP 2011, Lecture Notes in Computer Science, Vol. 6876 (Springer, Berlin, 2011), p. 2. https://doi.org/10.1007/978-3-642-23786-7_2CrossRef

18.

Zh. T. Qin, H. Zhu, and J. Ye, “Reinforcement learning for ridesharing: An extended survey,” Transp. Res. Part C: Emerging Technol. 144, 103852 (2022). https://doi.org/10.1016/j.trc.2022.103852CrossRef

19.

M. W. Savelsbergh, “The vehicle routing problem with time windows: Minimizing route duration,” ORSA J. Comput. 4, 146–154 (1992). https://doi.org/10.1287/ijoc.4.2.146CrossRefMATH

20.

M. M. Solomon, “Algorithms for the vehicle routing and scheduling problems with time window constraints,” Oper. Res. 35, 254–265 (1987). https://doi.org/10.1287/opre.35.2.254MathSciNetCrossRefMATH

21.

A. Vaswani, N. Shazeer, N. Parmar, J. Uszkoreit, L. Jones, A. N. Gomez, L. Kaiser, and I. Polosukhin, “Attention is all you need,” Adv. Neural Inf. Process. Syst. 30 (2017). https://doi.org/10.48550/arXiv.1706.03762

22.

T. Vidal, “Hybrid genetic search for the CVRP: Open-source implementation and swap* neighborhood,” Comput. Oper. Res. 140, 105643 (2022). https://doi.org/10.48550/arXiv.2012.10384MathSciNetCrossRefMATH

23.

T. Vidal, T. G. Crainic, M. Gendreau, N. Lahrichi, and W. Rei, “A hybrid genetic algorithm for multidepot and periodic vehicle routing problems,” Oper. Res. 60, 611–624 (2012). https://doi.org/10.1287/opre.1120.1048MathSciNetCrossRefMATH

24.

O. Vinyals, M. Fortunato, and N. Jaitly, “Pointer networks,” Adv. Neural Inf. Process. Syst. 28 (2015). https://doi.org/10.48550/arXiv.1506.03134

25.

G. Nemhauser and L. Wolsey, Integer and Combinatorial Optimization (John Wiley and Sons, 1999). https://doi.org/10.1002/9781118627372CrossRefMATH

Titel: Deep Reinforcement Learning for the Capacitated Pickup and Delivery Problem with Time Windows
verfasst von: A. G. Soroka
A. V. Meshcheryakov
S. V. Gerasimov
Publikationsdatum: 01.06.2023
Verlag: Pleiades Publishing
Erschienen in: Pattern Recognition and Image Analysis / Ausgabe 2/2023
Print ISSN: 1054-6618
Elektronische ISSN: 1555-6212
DOI: https://doi.org/10.1134/S1054661823020165

Springer Professional

Abstract

Bitte loggen Sie sich ein, um Zugang zu Ihrer Lizenz zu erhalten.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Wirtschaft"

Springer Professional "Technik"

Weitere Artikel der Ausgabe 2/2023

Tracking People in Video Using Neural Network Features and Facial Identification Taking into Account the Mask Mode

Systematics and Biases in Observations of Supernovae Associated with Gamma-Ray Bursts

Some Scientific Results of the XXIV International Conference DAMDID/RCDL-2022

Predictors Based on Convolutional Neural Networks for the Movement Strategy of Trainable Agents for Building Customized Image Descriptors

Cross-Correlation Methods in Problem of Search and Identification of Transient Objects in Astronomical Images

Image Neural Network Classifier by Detail Attributes

Premium Partner