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:
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).
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.
A specialized library for identifying best vehicle routes given constraints.
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.
data[‘pickups_deliveries’] = [
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’]
for request in data[‘pickups_deliveries’]:
pickup_index = manager.NodeToIndex(request)
delivery_index = manager.NodeToIndex(request)
routing.VehicleVar(pickup_index) == routing.VehicleVar(
For each pair, the command
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.
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.
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.