I'm trying to solve the Vehicle Route Optimisation with Time Window constraints using Google's OR Tools in Python. The problem here I'm solving is - I want to deliver packages to the customer, where the customers selects a specific time window for when they wish to receive the package (for examples between 10 AM to 11 AM). I have included a time_matrix for all 16 locations + depot. The code executes but it seems like the answer I'm getting isn't correct. I have included my code and the output I'm getting below.
Any help is really appreciated. I'm a beginner with Python and working on a project to optimise route with time window constraint.
Below, time_matrix table: is the time in minutes from one customer to other, time_windows table: here, depot is open from 9AM to 16(4PM) during the day. So I considered the start time as 0min and end time as 420min (60min * 7hours). And likewise calculated time for each customer
from ortools.constraint_solver import routing_enums_pb2
from ortools.constraint_solver import pywrapcp
import pandas as pd
def create_data_model():
data = {}
data["time_matrix"] = [
[0, 13, 9, 3, 7, 7, 10, 9, 6, 7, 7, 3, 8, 11, 9, 4, 4],
[13, 0, 3, 9, 6, 6, 5, 3, 5, 4, 5, 7, 4, 7, 4, 10, 11],
[9, 3, 0, 7, 5, 5, 4, 1, 4, 4, 4, 5, 3, 5, 3, 6, 8],
[3, 9, 7, 0, 4, 6, 7, 8, 5, 6, 6, 2, 4, 9, 8, 4, 3],
[7, 6, 5, 4, 0, 1, 4, 5, 6, 3, 2, 4, 1, 6, 4, 4, 4],
[7, 6, 5, 6, 1, 0, 5, 7, 6, 2, 2, 4, 2, 6, 4, 4, 4],
[10, 5, 4, 7, 4, 5, 0, 5, 7, 5, 5, 7, 5, 2, 2, 7, 5],
[9, 3, 1, 8, 5, 7, 5, 0, 3, 5, 4, 5, 4, 6, 4, 4, 8],
[6, 5, 4, 5, 6, 6, 7, 3, 0, 6, 6, 4, 6, 8, 7, 3, 9],
[7, 4, 4, 6, 3, 2, 5, 5, 6, 0, 2, 3, 4, 5, 4, 3, 6],
[7, 5, 4, 6, 2, 2, 5, 4, 6, 2, 0, 4, 3, 5, 3, 4, 5],
[3, 7, 5, 2, 4, 4, 7, 5, 4, 3, 4, 0, 5, 9, 5, 2, 4],
[8, 4, 3, 4, 1, 2, 5, 4, 6, 4, 3, 5, 0, 7, 5, 6, 4],
[11, 7, 5, 9, 6, 6, 2, 6, 8, 5, 5, 9, 7, 0, 3, 8, 8],
[9, 4, 3, 8, 4, 4, 2, 4, 7, 4, 3, 5, 5, 3, 0, 5, 8],
[4, 10, 6, 4, 4, 4, 7, 4, 3, 3, 4, 2, 6, 8, 5, 0, 6],
[4, 11, 8, 3, 4, 4, 5, 8, 9, 6, 5, 4, 4, 8, 8, 6, 0],
]
data["time_windows"] = [
(0, 420), # depot 9 - 16
(120, 180), # Customer 1 between: 11 - 12
(60, 120), # Customer 2 between: 10 - 11
(240, 300), # Customer 3 between: 13 - 14
(60, 120), # Customer 4 between: 10 - 11
(60, 120), # Customer 5 between: 10 - 11
(240, 300), # Customer 6 between: 13 - 14
(300, 360), # Customer 7 between: 14 - 15
(300, 360), # Customer 8 between: 14 - 15
(180 , 240), # Customer 9 between: 12 - 13
(120, 180), # Customer 10 between: 11 - 12
(300, 360), # Customer 11 between: 14 - 15
(240, 300), # Customer 12 between: 13 - 14
(240, 300), # Customer 13 between: 13 - 14
(120, 180), # Customer 14 between: 11 - 12
(60, 120), # Customer 15 between: 10 - 11
(60, 120), # Customer 16 between: 10 - 11
]
data["num_vehicles"] = 4
data["depot"] = 0
return data
def print_solution(data, manager, routing, solution):
print(f"Objective: {solution.ObjectiveValue()}")
time_dimension = routing.GetDimensionOrDie("Time")
total_time = 0
routes = []
for vehicle_id in range(data["num_vehicles"]):
index = routing.Start(vehicle_id)
route = []
plan_output = f"Route for vehicle {vehicle_id}:\n"
while not routing.IsEnd(index):
time_var = time_dimension.CumulVar(index)
node = manager.IndexToNode(index)
route.append((node, solution.Min(time_var), solution.Max(time_var)))
plan_output += (
f"{node} Time({solution.Min(time_var)},{solution.Max(time_var)}) -> "
)
index = solution.Value(routing.NextVar(index))
time_var = time_dimension.CumulVar(index)
node = manager.IndexToNode(index)
route.append((node, solution.Min(time_var), solution.Max(time_var)))
plan_output += (
f"{node} Time({solution.Min(time_var)},{solution.Max(time_var)})\n"
)
plan_output += f"Time of the route: {solution.Min(time_var)}min\n"
print(plan_output)
total_time += solution.Min(time_var)
routes.append(route)
print(f"Total time of all routes: {total_time}min")
# Exporting the solution to an Excel file
all_routes = []
for vehicle_id, route in enumerate(routes):
for node, start_time, end_time in route:
all_routes.append((vehicle_id, node, start_time, end_time))
df = pd.DataFrame(all_routes, columns=["Vehicle ID", "Node", "Start Time", "End Time"])
df.to_excel("PATH", index=False)
print("Solution exported to solution.xlsx")
def main():
data = create_data_model()
manager = pywrapcp.RoutingIndexManager(len(data["time_matrix"]),data["num_vehicles"],data["depot"])
routing = pywrapcp.RoutingModel(manager)
def time_callback(from_index, to_index):
from_node = manager.IndexToNode(from_index)
to_node = manager.IndexToNode(to_index)
return data["time_matrix"][from_node][to_node]
transit_callback_index = routing.RegisterTransitCallback(time_callback)
routing.SetArcCostEvaluatorOfAllVehicles(transit_callback_index)
# Adding a time window constraint
time = "Time"
routing.AddDimension(
transit_callback_index,
30, # maximum allowed waiting time
60, # maximum time allowed for a vehicle's journey
False, # the starting time does not have to be zero
time,
)
time_dimension = routing.GetDimensionOrDie(time)
# Add time window constraints for each customer except depot
for location_idx, time_window in enumerate(data["time_windows"]):
if location_idx == data["depot"]:
continue
index = manager.NodeToIndex(location_idx)
time_dimension.CumulVar(index).SetRange(time_window[0], time_window[1])
# Add time window constraints for each VEHICLE
depot_idx = data["depot"]
for vehicle_id in range(data["num_vehicles"]):
index = routing.Start(vehicle_id)
time_dimension.CumulVar(index).SetRange(data["time_windows"][depot_idx][0], data["time_windows"][depot_idx][1])
for i in range(data["num_vehicles"]):
routing.AddVariableMinimizedByFinalizer(time_dimension.CumulVar(routing.Start(i)))
routing.AddVariableMinimizedByFinalizer(time_dimension.CumulVar(routing.End(i)))
search_parameters = pywrapcp.DefaultRoutingSearchParameters()
search_parameters.first_solution_strategy = routing_enums_pb2.FirstSolutionStrategy.PATH_CHEAPEST_ARC
solution = routing.SolveWithParameters(search_parameters)
if solution:
print_solution(data, manager, routing, solution)
if __name__ == "__main__":
main()
When I execute this code, I get the below output, which doesn't look right to me.
Route for vehicle 0:
0 Time(0,0) -> 0 Time(0,0)
Time of the route: 0min
Route for vehicle 1:
0 Time(0,0) -> 0 Time(0,0)
Time of the route: 0min
Route for vehicle 2:
0 Time(0,0) -> 0 Time(0,0)
Time of the route: 0min
Route for vehicle 3:
0 Time(0,0) -> 11 Time(3,3) -> 15 Time(5,5) -> 8 Time(8,8) -> 7 Time(11,11) -> 2 Time(12,12) -> 12 Time(15,15) -> 4 Time(16,16) -> 5 Time(17,17) -> 10 Time(19,19) -> 9 Time(21,21) -> 1 Time(25,25) -> 14 Time(29,29) -> 13 Time(32,32) -> 6 Time(34,34) -> 16 Time(39,39) -> 3 Time(42,42) -> 0 Time(45,45)
Time of the route: 45min
Total time of all routes: 45min
There is no feasible / valid solution ever and a general rule in optimization is: don't process a solution without checking that it's status is valid! Anything can happen then (obviously depends on the solver-implementation) including indeterministic reading of uninitialized memory!
/// Returns the current status of the routing model.
Status status() const { return status_; }
/// Status of the search.
enum Status {
/// Problem not solved yet (before calling RoutingModel::Solve()).
ROUTING_NOT_SOLVED,
/// Problem solved successfully after calling RoutingModel::Solve().
ROUTING_SUCCESS,
/// Problem solved successfully after calling RoutingModel::Solve(), except
/// that a local optimum has not been reached. Leaving more time would allow
/// improving the solution.
ROUTING_PARTIAL_SUCCESS_LOCAL_OPTIMUM_NOT_REACHED,
/// No solution found to the problem after calling RoutingModel::Solve().
ROUTING_FAIL,
/// Time limit reached before finding a solution with RoutingModel::Solve().
ROUTING_FAIL_TIMEOUT,
/// Model, model parameters or flags are not valid.
ROUTING_INVALID,
/// Problem proven to be infeasible.
ROUTING_INFEASIBLE,
/// Problem has been solved to optimality.
ROUTING_OPTIMAL
};
Try:
solution = routing.SolveWithParameters(search_parameters)
print(routing.status())
With 9.7 the internal cp_solver will recognize your infeasibility during modelling! You don't even get to solve the problem then!
return _pywrapcp.IntExpr_SetRange(self, l, u)
Exception: CP Solver fail
With your time-windows configured as such, the globally earliest visit is at tick 60 (e.g. # Customer 2).
As you need to visit AND return, you will need > 60 ticks for each of your visits (because the first column in your matrix is strictly positive).
But with:
time = "Time"
routing.AddDimension(
transit_callback_index,
30, # maximum allowed waiting time
60, # maximum time allowed for a vehicle's journey
False, # the starting time does not have to be zero
time,
)
you basically limit the solvers horizon to 60 ticks.
'capacity' (here 60) is the upper bound of the cumul variables.
There is now a constraint which enforces the following:
/// Methods to add dimensions to routes; dimensions represent quantities
/// accumulated at nodes along the routes. They represent quantities such as
/// weights or volumes carried along the route, or distance or times.
/// Quantities at a node are represented by "cumul" variables and the increase
/// or decrease of quantities between nodes are represented by "transit"
/// variables. These variables are linked as follows:
/// if j == next(i), cumul(j) = cumul(i) + transit(i, j) + slack(i)
/// where slack is a positive slack variable (can represent waiting times for
/// a time dimension).
/// Setting the value of fix_start_cumul_to_zero to true will force the
/// "cumul" variable of the start node of all vehicles to be equal to 0.
/// Creates a dimension where the transit variable is constrained to be
/// equal to evaluator(i, next(i)); 'slack_max' is the upper bound of the
/// slack variable and 'capacity' is the upper bound of the cumul variables.
/// 'name' is the name used to reference the dimension; this name is used to
/// get cumul and transit variables from the routing model.
You cannot visit any node anymore and returning within 60 ticks. But your dimension-setup needs you to do it! (As you did not setup any disjunctions, every node-visit is mandatory)
Changing it to the following just for demo will show a solution with Status==1==ROUTING_SUCCESS i guess (although it does make little sense for you):
time = "Time"
routing.AddDimension(
transit_callback_index,
3000, # !!!
6000, # !!!
False, # the starting time does not have to be zero
time,
)