Tytuł pozycji:
Optymalizacja tras pojazdów z wykorzystaniem algorytmów kwantowych
Problem marszrutyzacji (optymalizacji trasy) jest kwintesencją problemu optymalizacji kombinatorycznej w badaniach operacyjnych, który ma głębokie implikacje dla logistyki, zarządzania łańcuchem dostaw i systemów transportowych. Jego celem jest określenie najbardziej efektywnych tras dla floty pojazdów do obsługi grupy klientów, biorąc pod uwagę różnego rodzaju ograniczenie, takie jak pojemność pojazdu, okna czasu dostawy i długość trasy. Skuteczne rozwiązanie problemów marszruty ma kluczowe znaczenie dla minimalizacji kosztów operacyjnych, skrócenia czasu dostaw i łagodzenia wpływu na środowisko. Jednakże złożoność tego typu obliczeń rośnie wykładniczo wraz z liczbą klientów i pojazdów, co sprawia, że znalezienie optymalnych rozwiązań w rozsądnych ramach czasowych dla klasycznych algorytmów staje się wyzwaniem obliczeniowym. Z drugiej strony, obliczenia kwantowe, oferują nowatorski paradygmat rozwiązywania złożonych problemów optymalizacyjnych, takich jak problem marszrutyzacji. W artykule zbadano zastosowanie algorytmów kwantowych do optymalizacji tras pojazdów, koncentrując się na ich potencjale w zakresie przezwyciężania ograniczeń klasycznych metod w obsłudze eksplozji kombinatorycznej charakterystycznej dla problemów marszrutyzacji. Zaproponowano podejście hybrydowe, łączące algorytm przybliżonej optymalizacji kwantowej z algorytmem optymalizacji za pomocą roju cząstek. Analizowano zagadnienie związane z wyznaczeniem optymalnych tras pojazdów, które miały obsłużyć 250 klientów. W implementacji kwantowego algorytmu optymalizacyjnego wykorzystano łącznie 251 kubitów. Uzyskane wyniki pokazują, że przy wykorzystaniu metod hybrydowych można skutecznie planować trasy pojazdów.
The vehicle routing problem (VRP) is a quintessential combinatorial optimization problem in operations research that has profound implications for logistics, supply chain management, and transportation systems. Its goal is to determine the most efficient routes for a fleet of vehicles to serve a group of customers, considering various constraints such as vehicle capacity, delivery time windows, and route length. Effectively solving VRP is crucial to minimizing operational costs, reducing delivery times, and mitigating environmental impacts. However, the complexity of this type of computation increases exponentially with the number of customers and vehicles, which makes finding optimal solutions within a reasonable time frame for classical algorithms a computational challenge. On the other hand, quantum computing (QC) offers a novel paradigm for solving complex optimization problems, such as the routing problem. In this paper, the QC application for vehicle route optimization, with a special emphasis on their potential to overcome the limitations of classical methods in handling the combinatorial explosion VRP characteristic has been studied. A hybrid approach was proposed combining an approximate quantum optimization algorithm with a particle swarm optimization algorithm. The problem of determining optimal vehicle routes to serve 250 customers was analyzed. A total of 251 qubits were used to implement the quantum optimization algorithm. The results obtained show that vehicle routes can be effectively planned using hybrid methods.
Opracowanie rekordu ze środków MNiSW, umowa nr POPUL/SP/0154/2024/02 w ramach programu "Społeczna odpowiedzialność nauki II" - moduł: Popularyzacja nauki (2025).
