Zadbaj o dobrą organizację dzięki kolekcji
Zapisuj i kategoryzuj treści zgodnie ze swoimi preferencjami.
Jednym z najczęstszych zadań optymalizacji jest wyznaczanie tras pojazdów, w ramach którego celem jest znalezienie najlepszych tras dla floty pojazdów odwiedzających określone lokalizacje. Zazwyczaj „najlepsza” oznacza trasy o najmniejszej odległości lub koszcie.
Oto kilka przykładów problemów z wyznaczaniem tras:
Firma kurierska chce przypisać kierowcom trasy, w których będą realizować dostawy.
Firma zajmująca się telewizją kablową chce wyznaczyć trasy technikom w celu nawiązywania połączeń z punktami usługowymi.
Firma oferująca wspólne przejazdy chce wyznaczyć trasy, w których kierowcy będą mogli wsiąść i wysiąść.
Najsłynniejszy problem z wyznaczaniem trasy to problem dotyczący podróżujących pracowników działu sprzedaży. Należy znaleźć najkrótszą trasę dla sprzedawcy, który musi odwiedzać klientów w różnych lokalizacjach i wracać do punktu początkowego. Dostawca usługi tokenów może być reprezentowany za pomocą wykresu, na którym węzły odpowiadają lokalizacjom, a krawędzie (lub łuki) – bezpośrednie przejazdy między lokalizacjami. Na przykład wykres poniżej przedstawia dostawcę usług tokenów z tylko 4 lokalizacjami oznaczonymi etykietami A, B, C i D.
Odległość między dowolnymi dwoma lokalizacjami jest określona przez liczbę obok łączącej je krawędzi.
Po obliczeniu odległości wszystkich możliwych tras widać, że najkrótsza trasa to ACDBA, dla której całkowita odległość wynosi 35 + 30 + 15 + 10 = 90.
Problem bardziej się komplikuje, gdy liczba lokalizacji jest większa. W powyższym przykładzie
istnieje tylko 6 tras. Jeśli jednak jest 10 lokalizacji (nie licząc punktu początkowego), liczba tras będzie wynosić 362 880.
W przypadku 20 lokalizacji numer zwiększa się do wartości 2432902008176640000.
Wyczerpujące przeszukanie wszystkich możliwych tras na pewno znajdzie najkrótszą trasę, ale w przypadku małych zbiorów lokalizacji obliczenia te mogą być trudne. W przypadku większych problemów potrzebne są techniki optymalizacji, które pozwolą na inteligentne przeszukanie przestrzeni rozwiązań i znalezienie optymalnego (lub prawie optymalnego) rozwiązania.
Bardziej ogólna wersja dostawcy usługi tokenów to problem z wyznaczaniem tras (VRP), w którym występuje wiele pojazdów. W większości przypadków platformy VRP podlegają pewnym ograniczeniom: na przykład pojazdy mogą mieć maksymalną wagę lub maksymalną ilość przewożonych przedmiotów, a kierowcy mogą być zobowiązani do wizyty w określonych przedziałach czasowych, o których klienci mówią klientom.
VRP z przedziałami czasu, w przypadku których pojazdy muszą odwiedzić lokalizacje w określonych odstępach czasu.
VRP z ograniczeniami zasobów, takimi jak przestrzeń lub personel na załadowanie i rozładowywanie pojazdów w zajezdni (punkt początkowy tras).
VRP w przypadku utraconych wizyt, w przypadku których pojazdy nie muszą odwiedzać wszystkich lokalizacji, ale muszą płacić za każdą wizytę w ramach utraconych wizyt.
Ograniczenia rozwiązywania problemów z wyznaczaniem tras pojazdów
Problemy z wyznaczaniem tras dla pojazdów są z natury nieuniknione: czas potrzebny na ich rozwiązanie rośnie wykładniczo z rozmiarem problemu. W przypadku wystarczająco dużych problemów znalezienie optymalnego rozwiązania może potrwać wiele lat. W efekcie OR-Tools zwraca czasami rozwiązania, które są dobre, ale nie optymalne. Aby znaleźć lepsze rozwiązanie, zmień jego opcje wyszukiwania. Przykład znajdziesz w sekcji Zmiana strategii wyszukiwania.
[null,null,["Ostatnia aktualizacja: 2024-08-09 UTC."],[[["\u003cp\u003eVehicle routing focuses on finding optimal routes for vehicles to visit locations, minimizing distance or cost, with applications like delivery services and ride-sharing.\u003c/p\u003e\n"],["\u003cp\u003eThe Traveling Salesperson Problem (TSP) seeks the shortest route for one vehicle to visit all locations and return to the starting point, becoming computationally complex with more locations.\u003c/p\u003e\n"],["\u003cp\u003eOR-Tools addresses various Vehicle Routing Problems (VRPs), including TSP, VRP with capacity and time constraints, and VRP with resource limitations and potential dropped visits.\u003c/p\u003e\n"],["\u003cp\u003eSolving VRPs can be computationally challenging, with solution times increasing exponentially with problem size, sometimes resulting in good but not optimal solutions from OR-Tools.\u003c/p\u003e\n"],["\u003cp\u003eWhile specialized solvers like Concorde excel at large TSPs, OR-Tools provides a more versatile platform for routing problems with constraints beyond the basic TSP.\u003c/p\u003e\n"]]],["Vehicle routing problems (VRPs) involve finding optimal routes for vehicles visiting locations, often minimizing total distance or cost. The Traveling Salesperson Problem (TSP) is a specific VRP with one vehicle. Solving these problems involves searching possible routes, with complexity increasing exponentially with more locations. OR-Tools, a routing solver, addresses various VRPs, including those with capacity, time, resource, and penalty constraints. While not always finding the absolute optimal solution, OR-Tools provides good solutions and users can adjust search strategies for better results.\n"],null,["# Vehicle Routing\n\n| **Note:** While the routing solver in Google's OR-Tools is free, users who need an industrial-class service can use the [Google Maps Platform Route Optimization API](https://developers.google.com/maps/documentation/route-optimization). Check out the [source code for a sample web application](https://github.com/googlemaps/js-route-optimization-app).\n\nOne of the most common optimization tasks is *vehicle routing*, in which the\ngoal is to find the best routes for a fleet of vehicles visiting a set of\nlocations. Usually, \"best\" means routes with the least total distance or cost.\nHere are a few examples of routing problems:\n\n- A package delivery company wants to assign routes for drivers to make deliveries.\n- A cable TV company wants to assign routes for technicians to make residential service calls.\n- A ride-sharing company wants to assign routes for drivers to pick up and drop off passengers.\n\nThe most famous routing problem is the *Traveling Salesperson Problem* (TSP):\nfind the shortest route for a salesperson who needs to visit customers at\ndifferent locations and return to the starting point. A TSP can be represented\nby a graph, in which the nodes correspond to the locations, and the edges (or\narcs) denote direct travel between locations. For example, the graph below shows\na TSP with just four locations, labeled A, B, C, and D.\nThe distance between any two locations is given by the number next to the edge\njoining them.\n\nBy calculating the distances of all possible routes, you can see that the\nshortest route is ACDBA, for which the total distance is `35 + 30 + 15 + 10 = 90`.\n\nThe problem gets harder when there are more locations. In the example above,\nthere are just six routes. But if there are ten locations (not counting the\nstarting point), the number of routes is 362880.\nFor 20 locations, the number jumps to 2432902008176640000.\nAn exhaustive search of all possible routes would be guaranteed to find the\nshortest, but this is computationally intractable for all but small sets of\nlocations. For larger problems, optimization techniques are needed to\nintelligently search the solution space and find an optimal (or near-optimal)\nsolution.\n\nA more general version of the TSP is the vehicle routing problem (VRP),\nin which there are multiple vehicles. In most cases, VRPs have constraints: for\nexample, vehicles might have capacities for the maximum weight or volume of items they\ncan carry, or drivers might be required to visit locations during specified time windows\nrequested by customers.\n\nOR-Tools can solve many types of VRPs, including the following:\n\n- [Traveling Salesperson Problem](/optimization/routing/tsp), the classic routing problem in which there is just one vehicle.\n- [Vehicle routing problem](/optimization/routing/vrp), a generalisation of the TSP with multiple vehicles.\n- [VRP with capacity constraints](/optimization/routing/cvrp), in which vehicles have maximum capacities for the items they can carry.\n- [VRP with time windows](/optimization/routing/vrptw), where the vehicles must visit the locations in specified time intervals.\n- [VRP with resource constraints](/optimization/routing/cvrptw_resources), such as space or personnel to load and unload vehicles at the depot (the starting point for the routes).\n- [VRP with dropped visits](/optimization/routing/penalties), where the vehicles aren't required to visit all locations, but must pay a penalty for each visit that is dropped.\n\nLimitations on solving vehicle routing problems\n-----------------------------------------------\n\nVehicle routing problems are inherently intractable: the length of time it takes\nto solve them grows exponentially with the size of the problem. For sufficiently\nlarge problems, it could take OR-Tools (or any other routing software) years to\nfind the optimal solution. As a result, OR-Tools sometimes returns solutions\nthat are good, but not optimal. To find a better solution, change the search\noptions for the solver. See [Changing the search strategy](/optimization/routing/tsp#search_strategy)\nfor an example.\n| **Note:** We should add that there are other solvers, such as [Concorde](http://www.math.uwaterloo.ca/tsp/concorde.html), dedicated to solving very large TSPs to optimality, which surpass OR-Tools in that area. However, OR-Tools provides a better platform for solving more general routing problems that contain constraints beyond those of a pure TSP."]]
