가장 일반적인 최적화 작업 중 하나는 차량 라우팅으로, 일련의 위치를 방문하는 여러 차량에 대한 최적의 경로를 찾는 것입니다. 일반적으로 '최적'은 총 거리 또는 비용이 가장 적은 경로를 의미합니다.
다음은 라우팅 문제의 몇 가지 예입니다.
택배 배송 회사에서 배송 기사에게 배송 경로를 지정하려고 합니다.
케이블 TV 회사에서 기술자가 가정에서 서비스 호출을 할 수 있는 경로를 할당하려고 합니다.
차량 공유 회사에서 운전자가 승객을 태우고 내릴 경로를 할당하려고 합니다.
가장 유명한 경로 문제는 여행 영업사원 문제 (TSP)입니다. 여러 위치에 있는 고객을 만나고 출발지로 돌아가야 하는 영업사원이 가장 짧은 경로를 찾는 것입니다. TSP는 그래프로 표시할 수 있습니다. 그래프에서는 노드가 위치에 해당하고 에지 (또는 원호)는 위치 간의 직접 이동을 나타냅니다. 예를 들어 아래 그래프는 A, B, C, D로 표시된 네 개의 위치만 있는 TSP를 보여줍니다.
두 위치 사이의 거리는 두 위치를 연결하는 가장자리 옆에 있는 숫자로 계산됩니다.
가능한 모든 경로의 거리를 계산하면 최단 경로가 ACDBA이며 총 거리는 35 + 30 + 15 + 10 = 90임을 알 수 있습니다.
위치가 많으면 문제가 더 어려워집니다. 위의 예에는 경로가 6개뿐입니다. 그러나 위치가 10개 (시작점을 포함하지 않는 경우)가 있는 경우 경로 수는 362880입니다.
20개 위치의 경우 숫자가 2432902008176640000으로 이동합니다.
가능한 모든 경로를 철저히 검색하면 최단 거리를 찾을 수 있지만 이는 일부 위치를 제외한 모든 위치에서 계산하기가 쉽지 않습니다. 더 큰 문제의 경우 솔루션 공간을 지능적으로 검색하고 최적의 (또는 최적에 가까운) 솔루션을 찾기 위한 최적화 기술이 필요합니다.
보다 일반적인 버전의 TSP는 여러 차량이 있는 차량 경로 문제 (VRP)입니다. 대부분의 경우 VRP에는 제약이 있습니다. 예를 들어 차량에 운반할 수 있는 최대 중량 또는 물량의 용량이 있을 수 있으며, 고객이 요청한 지정된 기간 동안 운전자가 위치를 방문해야 할 수도 있습니다.
방문이 중단된 VRP: 차량이 모든 위치를 방문할 필요는 없지만 방문이 중단될 때마다 위약금을 지불해야 합니다.
차량 경로 문제 해결 시 제한사항
차량 경로 문제는 본질적으로 다루기가 어렵습니다. 문제를 해결하는 데 걸리는 시간은 문제의 규모에 따라 기하급수적으로 증가합니다. 충분히 큰 문제의 경우 최적의 솔루션을 찾는 데 OR-Tools (또는 다른 라우팅 소프트웨어)가 몇 년이 걸릴 수 있습니다. 따라서 OR-Tools는 유용하지만 최적의 솔루션을 반환하는 경우가 있습니다. 더 나은 해법을 찾으려면 솔버의 검색 옵션을 변경하세요. 관련 예는 검색 전략 변경을 참조하세요.
[null,null,["최종 업데이트: 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."]]
