google ortools 로 경로 최적화 문제 풀기 (스압 주의)

본 포스팅에서는 구글에서 제공하는 최적화 오픈 소스 라이브러리인 ortools를 이용해 차량 경로 찾는 문제의 python 예제 코드를 소개하고자 한다. ortools 를 이용하면 한대의 차량이 다수의 방문지를 방문하는 Traveling salesman problem(TSP)부터 다수의 차량이 다수의 방문지를 방문하는 Vehicle Routing Problem(VRP), 그리고 VRP 가 변형된 다양한 경우의 최적화 문제를 풀 수 있다. 이 글에서는 기본 VRP부터 시작되어 이것이 변형되어 차량 용량 제약이 추가되었을때까지 보다 복잡한 VRP 문제 상황의 예제를 소개한다. (정확히는 공식 홈페이지에 제공된 예제를 해석하고 풀어 설명한다.) 

 

시작전에 교재 추천!

https://epubs.siam.org/doi/book/10.1137/1.9780898718515

 

Overview

In the Vehicle Routing Problem (VRP), the goal is to find optimal routes for multiple vehicles visiting a set of locations. (When there's only one vehicle, it reduces to the Traveling Salesman Problem.)

• VRP는 다수의 차량이 다수의 방문지를 방문하는 "최적"의 경로를 찾는 문제이다. 차량 대수가 1대일때는 TSP 이다. 

But what do we mean by "optimal routes" for a VRP? One answer is the routes with the least total distance. However, if there are no other constraints, the optimal solution is to assign just one vehicle to visit all locations, and find the shortest route for that vehicle. This is essentially the same problem as the TSP.

• 그렇다면 "최적의 경로" 라는 것은 무엇일까? 이동 경로의 총 합을 최소화하는 경로를 생각해볼 수 있다. 하지만 주의할 점은 만일 별도의 제약 조건이 없다면 다수의 차량의 최적의 경로 문제를 풀면 사실상 1대의 차량이 모든 방문지를 도는것이 최적의 경로라는 해답을 얻게될 것이라는 점이다. 이것은 TSP를 푼것이나 다름 없으므로 의미가 없다. 

A better way to define optimal routes is to minimize the length of the longest single route among all vehicles. This is the right definition if the goal is to complete all deliveries as soon as possible. The VRP example below finds optimal routes defined this way.

• 따라서 더 나은 방법은 모든 차량 중 가장 이동경로가 긴 차량의 경로를 최소화하는 것이다. 이것은 모든 delivery가 최대한 빨리 완료되도록 하는 목적하에서 적합한 문제 정의이다. 

VRP example

• 아래 그림은 방문지가 파란색, 차고지가 검정색으로 표시된다. 예제를 살짝 변형하면 방문지와 차고지가 있는 network를 내 마음대로 짤 수 있다는 사실을 알 수 있다. 

 

Define the distance callback

As in the TSP example, the following function creates the distance callback, which returns the distances between locations, and passes it to the solver.

• distance callback이라는 함수는 특정 지점의 index를 넣어주면 실제 두 점 사이의 거리를 ouput 으로 내보내주는 함수이다. 
• pywrapcp.RoutingIndexManager 라는 함수는 말그대로 인덱스를 관리해준다. 인자를 보면 (1) depot+방문지 개수 (depot+방문지를 list로 따졌을때 인덱스 수가 됨) (2) 차량 대수 (3) depo 에 해당하는 인덱스이다. 이렇게 생성한 함수를 manager라 칭한다.
• 아까 정의한 manager은 IndexToNode 라는 함수를 가지고 있는 모양이다. 출발과 도착의 index를 받으면(이게 어떤형태지?) 그것을 node 번호로 변환시켜주어 distance matrix 상에서의 index로 변환시켜준다. 

def create_data_model():
    """Stores the data for the problem."""
    data = {}
    data['distance_matrix'] = [
        생략
    ]  # yapf: disable
    data['num_vehicles'] = 1
    data['depot'] = 0
    return data

data = create_data_model()
manager = pywrapcp.RoutingIndexManager(len(data['distance_matrix']),
                                       data['num_vehicles'], data['depot'])
routing = pywrapcp.RoutingModel(manager)

def distance_callback(from_index, to_index):
    """Returns the distance between the two nodes."""
    # Convert from routing variable Index to distance matrix NodeIndex.
    from_node = manager.IndexToNode(from_index)
    to_node = manager.IndexToNode(to_index)
    return data['distance_matrix'][from_node][to_node]

 It also sets the arc costs, which define the cost of travel, to be the distances of the arcs.

• 이것은 arc 의 거리, 즉 cost of travel 도 정의해준다.

transit_callback_index = routing.RegisterTransitCallback(distance_callback)
routing.SetArcCostEvaluatorOfAllVehicles(transit_callback_index)

 

Add a distance dimension

To solve this VRP, you need to create a distance dimension, which computes the cumulative distance traveled by each vehicle along its route. You can then set a cost proportional to the maximum of the total distances along each route. Routing programs use dimensions to keep track of quantities that accumulate over a vehicle's route. See Dimensions for more details.

• 이 routing solver는 'dimension'이란 오브젝트를 필요로 한다.
• 'distance dimension'는 각 차량이 경로를 따라 이동함에따라 누적되는 거리/시간를 계산해내는데 필요하다. 
• 다른 'dimension'의 예시로는 각 차량이 pickup and delivery를 할때 차량안에있는 item의 수 이다. 

 

잠깐 dimension에 대해서 더 알아보자. 

---

Examples of dimensions

Here are a couple of examples of dimensions from previous sections.

• The VRPTW example creates a dimension to track each vehicle's cumulative travel time. The solver uses the dimension to enforce the constraint that a vehicle can only visit a location within the location's time window.
• The CVRP example creates a dimension for the demands (e.g., weights or volumes of packages to be picked up), which tracks the cumulative load the vehicle is carrying along its route. The solver uses the dimension to enforce the constraint that a vehicle's load can't exceed its capacity.

 

• VRP에 time window를 추가한 예시에서는 각 차량의 누적된 이동 시간을 구할때 dimension 오브젝트를 사용한다. solver는 차량이 특정 time window 내에 있을때만 해당 장소를 방문하도록 제약 조건을 거는데에 사용된다.
• 트럭의 용량이 있는 경우 트럭이 싣고있는 누적된 item의 값을 구하는데 dimension을 사용한다. solver는 차량에 싣고있는 item의 양이 트럭 용량을 나타낸다. 

The examples below define a dimension for the VRPTW using the AddDimension method.

routing.AddDimension(
    callback_index,
    slack_max,
    capacity,
    fix_start_cumul_to_zero,
    dimension_name)

The AddDimension method has the following inputs:

• callback_index: The index for the callback that returns the quantity. The index, which is the solver's internal reference to the callback, is created by methods such as RegisterTransitCallback or RegisterUnitaryTransitCallback.
• slack_max: Maximum for the slack, a variable used to represent waiting times at the locations. See slack variables below for details. If the problem doesn't involve waiting time, you can usually set slack_max to 0.
• capacity: Maximum for the total quantity accumulated along each route. Use capacity to create constraints like those in the CVRP. If your problem doesn't have such a constraint, you can set capacity to a value that is sufficiently large to impose no restrictions on the routes—for example, the sum of all entries of the matrix or array used to define the callback.
• fix_start_cumulative_to_zero: Boolean value. If true, the cumulative value of the quantity starts at 0. In most cases, this should be set to True. However, for the VRPTW or problems with resource constraints, some vehicles may have to start after time 0 due to time window constraints, so you should setfix_start_cumulative_to_zero to False for these problems.
• dimension_name: String for the name for the dimension, such as 'Distance', which you can use to access the variables elsewhere in the program.

AddDimension이라는 함수의 input은 다음 5가지가 있다. 

• callback_index: 수량을 돌려주는 callback 의 인덱스를 의미한다. (??)
• slack_max: slack 의 maximum 값. 특정 장소에서의 대기시간의 maximum값을 나타낸다. 만일 대기시간을 설정하고 싶지 않다면 slack_max를 0이라고 설정하면 된다. slack 에 대해서는 뒤에서 자세하게 설명하겠다. 
• capacity: 차량 용량. 만일 차량 용량을 고려하고 싶지 않다면 충분히 큰 수로 설정하면 된다. 
• fix_start_cumul_to_zero: True 혹은 False를 가지는 Boolean 값이다. True 일때는 트럭에 싣고 있는 item 의 수의 초기값 혹은 time이 0으로 설정된다. 
• dimemsion_name: 나중에 접근할 수 있도록 dimension에 이름을 붙여준다. 나중에 접근은 

 

The CVRP program creates a slightly different type of dimension using the the AddDimensionWithVehicleCapacity method. This method takes an array of capacities, with one entry for each vehicle. (In contrast, AddDimension takes a single value for capacity, so all vehicles are assumed to have the same capacity.)

• 앞서 설명한 AddDimension은 모든 차량이 동일한 용량을 가진다고 가정한다. 만일 차량이 여러대일때 각 차량별로 다른 용량을 설정하고싶다면 AddDimensionWithVehicleCapacity 를 사용하라. 

See the RoutingModel reference page for other methods that create dimensions.

• 다른 종류의 dimension을 생성할 수 있는 다양한 방법이 있다. 아래 링크를 참고하자. 
• https://developers.google.com/optimization/reference/constraint_solver/routing/RoutingModel

The section Save the solution time windows to a list or array presents functions that save the cumulative data in a dimension in a list or array.

• 누적 데이터를 list 나 array로 보관할 수 있는 방법은 이 링크를 참고하자. 

Slack variables

Here's an example that illustrates slack variables for a problem involving travel time. Suppose that a vehicle goes from location i to location j in one step of its route, and that:

• time window가 포함된 VRP 상황에서 slack variable이 어떻게 사용되는지를 알아보겠다. 

 

• The vehicle's cumulative travel time at i is 100 minutes.
• The vehicle's cumulative travel time at j is 200 minutes.
• The travel time from i to j is 75 minutes.

The vehicle can't leave location i immediately upon arrival, or its cumulative time at location j would be 175. Instead, vehicle must wait for 25 minutes at location i before departing; in other words, the slack at location i is 25.

• 만일 어떤 차량이 시작 시간으로부터 100분이 지나기 전에 i 위치에 도달해야하고 200분이 지나기 전에는 j 위치에 도달해야한다고 가정해보자. 그리고 i 위치에서 j 위치로 가는데는 75분이 걸린다. 그럼 100분일때 i 위치를 출발한 차량이 j 위치에 도달하면 175분이므로 25분의 공백이 생긴다. 차량은 25분 대기하는 여유시간이 있어야한다. 

 

You need to allow slack in a VRPTW because vehicles may have to wait before visiting a location, due to time window constraints. In a problem like this, set slack_max to the maximum amount of time you want to allow vehicles to wait at a location before proceeding to the next location. If it doesn't matter how long they wait, just set slack_max to a very large number.

• 차량이 얼마나 오래 기다리는지는 중요한 문제가 아니라면 역시나 slack_max를 충분히 큰 숫자로 설정하면 된다. 

For the CVRP, on the other hand, the change in the accumulated load from i to j always equals the demand at i, so there is no slack. For problems like this, you can set slack_max to 0.

• 차량 용량의 관점에서 보면 차량이 i 에서 j 로 이동할때 누적된 load의 변화는 i에서의 수요와 같다. 따라서 이 경우 max_slack을 0으로 설정하면 된다. 

Next, we'll give the formal definition of slack. Internally, a dimension stores two types of variables related to quantities that accumulate along routes:

• Transit variables: The increase or decrease of the quantity at each step of a route. If i -> j is one step in a route, the transit variable is either the i, j entry of the transit matrix (for a transit callback), or simply the callback value at location i (if the callback depends on just one location).
• Cumulative variables: The total accumulated quantity at each location. You can access the cumulative variable at location i by dimension_name.CumulVar(i). For an example, see the time window constraints in the VRPTW example.

 

• slack에 대해 공식적으로 정의를 해보자면 dimension 오브젝트는 차량의 route 를 따라 이동함에 따라 '누적되는 수량'과 관련한 두가지 타입의 변수를 저장한다. 
• Transit variables: 방문지 i 에서 j 의 이동이 하나의 step이라 할때, 각 스텝에서 증가하거나 감소하는 수량의 숫자. 
• Cumulative variables: 각 장소에서 누적된 수량. dimension 이름.CumulVar(i) 라 하면 누적된 양에 접근 할 수 있다. 

Assuming that a vehicle goes from location i to location j in one step, the slack is related to these variables as follows:

slack(i) = cumul(j) - cumul(i) - transit(i, j)

• 따라서 slack variable와 누적 수량의 관계는 다음과 같다. 

---

돌아와서 VRP 예제를 다시 보자. 

The following code creates the distance dimension, using the solver's AddDimension method. The argument transit_callback_index is the index for the distance_callback.

dimension_name = 'Distance'
routing.AddDimension(
    transit_callback_index,
    0,  # no slack
    3000,  # vehicle maximum travel distance
    True,  # start cumul to zero
    dimension_name)
distance_dimension = routing.GetDimensionOrDie(dimension_name)
distance_dimension.SetGlobalSpanCostCoefficient(100)

The method SetGlobalSpanCostCoefficient sets a large coefficient (100) for the global span of the routes, which in this example is the maximum of the distances of the routes. This makes the global span the predominant factor in the objective function, so the program minimizes the length of the longest route. 

• 위 예제 코드에서는 Distance dimension을 추가한다. 기다리는 것은 허용하지 않고 travel distance도 충분히 크게 설정했으며 0에서 부터 시작하는 아주 일반적인 형태의 dimension이다. 
• 이렇게 정의된 dimension 은 이름을 GetDimensionOrDie를 사용해 routing 에 넣어준다. 

 

Add the solution printer

The function that prints the solution is shown below.

def print_solution(data, manager, routing, solution):
  """Prints solution on console."""
  max_route_distance = 0
  for vehicle_id in range(data['num_vehicles']):
    index = routing.Start(vehicle_id)
    plan_output = 'Route for vehicle {}:\n'.format(vehicle_id)
    route_distance = 0
    while not routing.IsEnd(index):
      plan_output += ' {} -> '.format(manager.IndexToNode(index))
      previous_index = index
      index = solution.Value(routing.NextVar(index))
      route_distance += routing.GetArcCostForVehicle(previous_index, index,
                                                     vehicle_id)
    plan_output += '{}\n'.format(manager.IndexToNode(index))
    plan_output += 'Distance of the route: {}m\n'.format(route_distance)
    print(plan_output)
    max_route_distance = max(route_distance, max_route_distance)
  print('Maximum of the route distances: {}m'.format(max_route_distance))

The function displays the routes for the vehicles and the total distances of the routes.

Alternatively, you can first save the routes to a list or array, and then print them.

~~

---

Overview of Capacitated Vehicle Routing Problem

The capacitated vehicle routing problem (CVRP) is a VRP in which vehicles with limited carrying capacity need to pick up or deliver items at various locations. The items have a quantity, such as weight or volume, and the vehicles have a maximum capacity that they can carry. The problem is to pick up or deliver the items for the least cost, while never exceeding the capacity of the vehicles.

• 차량이 특정 item 을 pick up or deliver 하는 상황을 다룸.
• 특정 item은 무게나 부피 등 quantity가 있음. 
• 차량은 한번에 옮길 수 있는 maximum capacity 있음 

Note: In the following example, we assume that all items are being picked up. The program that solves this problem also works if all items are being delivered: in this case, you can think of the capacity constraint being applied when the vehicles leave the depot fully loaded. But the capacity constraints are implemented the same way in both cases.

For a related example in which there are both pickups and deliveries, see Pickups and Deliveries.

• 이 예시는 다수의 방문지에 있는 모든 item이 차량에 의해 전부 pick up 혹은 delivery 되어야만 하는 예제임. 차량이 depot (정거장, 창고)를 떠난 시점부터 용량 제약이 작용한다고 볼 수 있음. (Pickups & deliveries 가 모두 고려되어야하는 상황은 다른 예제에 있음. 
• 우선은 모든 item이 pickup 되어야한다고 가정하고 예제를 진행하겠음.

CVRP example

Next, we describe an example of a VRP with capacity constraints. The example extends the previous VRP example and adds the following requirements. At each location there is a demand corresponding to the quantity of the item to be picked up. Also, each vehicle has a maximum capacity of 15. (We aren't specifying units for the demands or capacity.)

• 각각의 방문지에 pick up 되어야하는 item의 양이 'demand'로 제시됨.
• 차량 용량은 15라고 가정함. (본 예제에서는 차량이 4대라는 가정이 있다.)

The grid below shows the locations to visit in blue and the company location in black. The demands are shown at the lower right of each location. See Location coordinates in the VRP section for more details about how the locations are defined.

The problem is to find an assignment of routes to vehicles that has the shortest total distance, and such that the total amount a vehicle is carrying never exceeds its capacity.

• 아래 그림은 방문지가 파란색, 차고지가 검정색으로 표시됨. 빨간색으로 표시되어있는건 각 지점의 demand 임. 
• 본 최적화 문제는 차량이 옮겨주는 화물이 차량 용량을 넘지 않는다는 제약 하에 트럭의 총 이동거리를 최소화하는 경로를 찾아주는 문제이다.

Solving the CVRP example with OR-Tools

The following sections explain how to solve the CVRP example with OR-Tools.

Create the data

The data for this example includes the data in the previous VRP example, and adds the following demands and vehicle capacities:

data['demands'] = [0, 1, 1, 2, 4, 2, 4, 8, 8, 1, 2, 1, 2, 4, 4, 8, 8]
data['vehicle_capacities'] = [15, 15, 15, 15]

• 위와같이 1개의 depot와 16개의 방문지가 있는 상황에서 총 17개의 demand를 리스트형태로 정의해준다. depot에는 수요가 0이고 나머지에는 양의 수요가 발생한다. 
• 4개의 트럭의 용량을 리스트 형태로 각각 정의한다

Add the distance callback

The distance callback—the function that returns the distance between any two locations—is defined the same way as in the previous VRP example.

• 두 지점을 input 으로 받으면 output 으로 두점사이의 거리를 주는 함수를 정의한다.

Add the demand callback and capacity constraints

In addition to the distance callback, the solver also requires a demand callback, which returns the demand at each location, and a dimension for the capacity constraints. The following code creates these.

• 아까는 distance callback을 정의한 것과 마찬가지로 여기서는 demand callback이 필요하다. 여기서는 방문지 하나의 index를 받으면 demand 를 돌려준다. 
• 정의된 demand callback을 이용해 AddDimension 까지 해준다. 위와의 하나 다른 점은 목적인데 이 예제에서는 각 방문지의 demand를 이용해 누적 load가 차량 용량을 넘지 않도록 해주는 것이 목적이다. 

def demand_callback(from_index):
    """Returns the demand of the node."""
    # Convert from routing variable Index to demands NodeIndex.
    from_node = manager.IndexToNode(from_index)
    return data['demands'][from_node]

demand_callback_index = routing.RegisterUnaryTransitCallback(demand_callback)
routing.AddDimensionWithVehicleCapacity(
    demand_callback_index,
    0,  # null capacity slack
    data['vehicle_capacities'],  # vehicle maximum capacities
    True,  # start cumul to zero
    'Capacity')

• CVRP를 풀면 위와 같이 경로가 나온다. 차량이 다수의 방문지를 돌며 pickup 하는 경우의 예제이다. 
• 아래는 위 그림에 상응하는 자세한 경로정보를 text로 받은 모습이다. 

 

What happens if a problem has no solution?

A routing problem with constraints, such as a CVRP, might not have a feasible solution— for example, if the total quantity of the items being transported exceeds the total capacity of the vehicles. If you try to solve such a problem, the solver might run an exhaustive search which takes so long that eventually you have to give up and interrupt the program.

Usually this won't be an issue. But here are a couple of ways to prevent your program from running a long time when a problem has no solution:

• Set a time limit in the program, which stops the search even if no solution has been found. However, keep in mind that if the problem has a solution that requires a lengthy search, the program might reach the time limit before finding the solution.
• Set penalties for dropping visits to locations. This allows the solver to return a "solution" that doesn't visit all locations in case the problem is infeasible. See Penalties and Dropping Visits.

 

• CVRP와 같은 제약 조건이 존재하는 routing problem은 feasible solution를 구할 수 없는 상황이 벌어지기도 한다. (이런경우 프로그램이 멈추지 않아 최적해를 구하지 못한채 커널을 강제 중단 시켜야한다. 
• 이 경우를 해결할 수 있는 방법이 두개가 있는데 (1) time limit 설정하기와 (2) 모든 방문지를 방문하는것이 infeasible할 경우 몇개의 방문지를 drop 할 수 있도록 허용하고 대신 패널티를 주는 방식이다. 

In general, it can be hard to tell if a given problem has a solution. Even for a CVRP in which total demand doesn't exceed total capacity, determining whether all the items will fit in the vehicles is a version of the multiple knapsack problem.

일반적으로 해가 있는지 없는지 한번에 판단하기는 어렵다. 만일 정확히 진단하고싶다면 multiple knapsack problem을 이용해 진단해야한다. 

 

출처 

CVRP

https://developers.google.com/optimization/routing/vrp

Capacity Constraints  |  OR-Tools  |  Google Developers