VRPTW with battery waiting and charging at depot

[Zouitine Mehdi]

Hello everybody,

I’m trying to model a specific version of the VRPTW in OR-Tools:

• No waiting at customers → service must start immediately when arriving.

• Battery/energy constraint → consumption proportional to distance.

• Charging at depots → the vehicle may return to a depot multiple times during its route, and when it does, it can wait/charge. The solver should decide if and how long to stay.

• To model this, I synchronize time slack = battery slack at depots.

Here’s a minimal example:

from ortools.constraint_solver import pywrapcp, routing_enums_pb2

def create_data_model():

data = {}

# Distance/time matrix with depot duplicated 3 times (0,4,5 are depot nodes)

data['time_matrix'] = [

[0, 2, 2, 2, 0, 0], # depot0

[2, 0, 2, 2, 2, 2], # cust1

[2, 2, 0, 2, 2, 2], # cust2

[2, 2, 2, 0, 2, 2], # cust3

[0, 2, 2, 2, 0, 0], # depot1

[0, 2, 2, 2, 0, 0], # depot2

]

data['time_windows'] = [

(0, 100), # depot0

(2, 4), # cust1

(10, 12), # cust2

(6, 8), # cust3

(0, 100), # depot1

(0, 100), # depot2

]

data['battery_matrix'] = data['time_matrix'] # consumption proportional to distance

data['max_battery'] = 10000

data['num_vehicles'] = 1

data['depot'] = 0

return data

def main():

data = create_data_model()

manager = pywrapcp.RoutingIndexManager(

len(data['time_matrix']), data['num_vehicles'], data['depot'])

routing = pywrapcp.RoutingModel(manager)

# Time callback

def time_callback(from_index, to_index):

return data['time_matrix'][manager.IndexToNode(from_index)][manager.IndexToNode(to_index)]

time_callback_index = routing.RegisterTransitCallback(time_callback)

routing.SetArcCostEvaluatorOfAllVehicles(time_callback_index)

# Battery callback

def battery_callback(from_index, to_index):

return data['battery_matrix'][manager.IndexToNode(from_index)][manager.IndexToNode(to_index)]

battery_callback_index = routing.RegisterTransitCallback(battery_callback)

# Time dimension

routing.AddDimension(

time_callback_index,

100, # slack allowed

100, # horizon

False,

"Time")

time_dimension = routing.GetDimensionOrDie("Time")

# Battery dimension

routing.AddDimension(

battery_callback_index,

data['max_battery'], # slack = charging

data['max_battery'], # capacity

False, # don't force start to 0

"Battery")

battery_dimension = routing.GetDimensionOrDie("Battery")

# Apply time windows

for node, (start, end) in enumerate(data['time_windows']):

index = manager.NodeToIndex(node)

time_dimension.CumulVar(index).SetRange(start, end)

# No waiting or charging at customers

for node in range(1, 4):

index = manager.NodeToIndex(node)

routing.solver().Add(time_dimension.SlackVar(index) == 0)

routing.solver().Add(battery_dimension.SlackVar(index) == 0)

# Synchronize time slack == battery slack at depots

depot_nodes = [0, 4, 5]

for node in depot_nodes:

index = manager.NodeToIndex(node)

routing.solver().Add(

time_dimension.SlackVar(index) == battery_dimension.SlackVar(index)

)

# Forbid direct depot-to-depot arcs

for i in depot_nodes:

for j in depot_nodes:

if i != j:

routing.solver().Add(

routing.NextVar(manager.NodeToIndex(i)) != manager.NodeToIndex(j)

)

# Force depot start node to full battery

start_index = routing.Start(0)

battery_dimension.CumulVar(start_index).SetValue(data['max_battery'])

# Solve

search_parameters = pywrapcp.DefaultRoutingSearchParameters()

search_parameters.first_solution_strategy = (

routing_enums_pb2.FirstSolutionStrategy.PATH_CHEAPEST_ARC)

search_parameters.local_search_metaheuristic = (

routing_enums_pb2.LocalSearchMetaheuristic.GUIDED_LOCAL_SEARCH)

search_parameters.time_limit.seconds = 5

solution = routing.SolveWithParameters(search_parameters)

if solution:

time_var = time_dimension.CumulVar

battery_var = battery_dimension.CumulVar

index = routing.Start(0)

plan = []

while not routing.IsEnd(index):

node = manager.IndexToNode(index)

t = solution.Value(time_var(index))

b = solution.Value(battery_var(index))

plan.append(f"Node {node} at time {t}, battery {b}")

index = solution.Value(routing.NextVar(index))

node = manager.IndexToNode(index)

t = solution.Value(time_var(index))

b = solution.Value(battery_var(index))

plan.append(f"Node {node} at time {t}, battery {b}")

plan.append("End")

print(" -> ".join(plan))

else:

print("No solution found!")

if __name__ == "__main__":

main()