About OR-Tools

OR-Tools is open source software for combinatorial optimization, which seeks to find the best solution to a problem out of a very large set of possible solutions. Here are some examples of problems that OR-Tools solves:

Vehicle routing: Find optimal routes for vehicle fleets that pick up and deliver packages given constraints (e.g., “this truck can’t hold more than 20,000 pounds” or “all deliveries must be made within a two-hour window”).

Scheduling: Find the optimal schedule for a complex set of tasks, some of which need to be performed before others, on a fixed set of machines, or other resources.

Bin packing: Pack as many objects of various sizes as possible into a fixed number of bins with maximum capacities.

In most cases, problems like these have a vast number of possible solutions—too many for a computer to search them all. To overcome this, OR-Tools uses state-of-the-art algorithms to narrow down the search set, in order to find an optimal (or close to optimal) solution.

OR-Tools includes solvers for:

Constraint Programming

A set of techniques for finding feasible solutions to a problem expressed as constraints (e.g., a room can’t be used for two events simultaneously, or the distance to the crops must be less than the length of the hose, or no more than five TV shows can be recorded at once).

Linear and Mixed-Integer Programming

The Glop linear optimizer finds the optimal value of a linear objective function, given a set of linear inequalities as constraints (e.g., assigning people to jobs, or finding the best allocation of a set of resources while minimizing cost). Glop and the mixed-integer programming software SCIP are also available via both Google Sheets and Google Apps Script.

Vehicle Routing

A specialized library for identifying best vehicle routes given constraints.

Graph Algorithms

Code for finding shortest paths in graphs, min-cost flows, max flows, and linear sum assignments.

The next section will get you started using OR-Tools quickly.

 

 

Vehicle Routing with Pickups and Deliveries

In this section we describe a VRP in which each vehicle picks up items at various locations and drops them off at others. The problem is to assign routes for the vehicles to pick up and deliver all the items, while minimizing the length of the longest route.

Solving the example with OR-Tools

The following sections describe how to solve the VRP with pickups and deliveries. Much of the code is borrowed from the previous VRP example, so we’ll focus on the parts that are new.

Create the data

The data for the problem includes the distance matrix from the previous VRP example, along with a list of pairs of pickup and delivery locations, data[‘pickups_deliveries’], corresponding to the directed edges in the diagram above. The code below defines the pickup and delivery locations.

PythonC++JavaC#

data[‘pickups_deliveries’] = [
[1, 6],
[2, 10],
[4, 3],
[5, 9],
[7, 8],
[15, 11],
[13, 12],
[16, 14],
]

For each pair, the first entry is index of the pickup location, and the second is the index of the delivery location.

Define pickup and delivery requests

The following code defines pickup and delivery requests, using pickup and delivery locations in data[‘pickups_deliveries’]

PythonC++JavaC#

for request in data[‘pickups_deliveries’]:
pickup_index = manager.NodeToIndex(request[0])
delivery_index = manager.NodeToIndex(request[1])
routing.AddPickupAndDelivery(pickup_index, delivery_index)
routing.solver().Add(
routing.VehicleVar(pickup_index) == routing.VehicleVar(
delivery_index))
routing.solver().Add(
distance_dimension.CumulVar(pickup_index) <=
distance_dimension.CumulVar(delivery_index))

For each pair, the command

routing.AddPickupAndDelivery(pickup_index, delivery_index)

creates a pickup and delivery request for an item.

The following line adds the requirement that each item must be picked up and delivered by the same vehicle.

routing.solver().Add(
routing.VehicleVar(pickup_index) ==
routing.VehicleVar(delivery_index))

Finally, we add the obvious requirement that each item must be picked up before it is delivered. To do so, we require that a vehicle’s cumulative distance at an item’s pickup location is at most its cumulative distance at the delivery location.

routing.solver().Add(
distance_dimension.CumulVar(pickup_index) <=
distance_dimension.CumulVar(delivery_index))

Running the program

The complete programs for the VRP with pickups and deliveries are shown in the next section. When you run the program, it displays the routes.

 

 

Post Comment

Your email address will not be published. Required fields are marked *

This site uses Akismet to reduce spam. Learn how your comment data is processed.