# Primary objective: Minimize total distance (higher priority)
model.setObjectiveN(
quicksum(
euclidean_dist(i, j) * model.x[k, i, j]
for k in model.K
for i, j in model.A
),
index=0,
priority=2,
name=OBJ_MINIMIZE_DISTANCE,
)
# Secondary objective: Minimize total delay (lower priority)
model.setObjectiveN(
quicksum(
model.B[k][i] - model.e[i]
for k in model.K
for i in model.P + model.D
),
index=1,
priority=1,
name=OBJ_MINIMIZE_TOTAL_DELAY,
)4 Multi-Objective Optimization for the Dial-a-Ride Problem
A tutorial on multi-objective optimization using Gurobi for the DARP.
Keywords
DARP, multi-objective optimization, Gurobi, vehicle routing, optimization modeling, goal programming, hierarchical optimization, weighted sum method
4.1 Learning Objectives
- Understand the formulation of the Dial-a-Ride Problem (DARP) and its constraints.
- Learn how to implement multi-objective optimization using Gurobi for the DARP.
- Explore different approaches to multi-objective optimization, including linear combinations of objectives and hierarchical optimization.
- Propose instances of the DARP that help identify trade-offs between different objectives, such as minimizing total distance and minimizing total delay.
4.2 Introduction
The Dial-a-Ride Problem (DARP) is a well-known vehicle routing problem that involves transporting passengers between pickup and delivery locations. Typically, the goal is to minimize the total travel distance or time while satisfying constraints such as vehicle capacity, time windows, and precedence relationships between pickup and delivery nodes.
4.3 Problem Description
The DARP consists of the following elements:
- Nodes: Depots, pickup nodes, and delivery nodes.
- Vehicles: A fleet with limited capacity.
- Requests: Each request includes one pickup and its corresponding delivery.
- Constraints:
- Capacity: Vehicles cannot exceed a defined load.
- Time Windows: Each node has an earliest and latest service time.
- Precedence: A pickup must occur before its paired delivery.
- Objectives: Typically, minimizing total travel distance or time, minimizing total delay, or a combination of both.
- Distance Function: A function to calculate the distance between two nodes.
4.4 DARP Formulation
Sets and Indices
- \(i, j\): Indices for nodes, including pickup and drop-off points.
- \(k\): Index for vehicles.
- \(P\): Set of pickup nodes.
- \(D\): Set of drop-off nodes.
- \(K\): Set of vehicles.
Parameters
- \(n\): Number of users (requests).
- \(Q\): Capacity of each vehicle.
- \(T\): Maximum duration of any route.
- \(L\): Maximum ride time for a user.
- \(c_{ij}\): Travel cost from node \(i\) to node \(j\).
- \(t_{ij}\): Travel time from node \(i\) to node \(j\).
- \(e_i, l_i\): Earliest and latest service time for node \(i\).
- \(d_i\): Service duration at node \(i\).
- \(q_i\): Demand of user associated with node \(i\) (often 1 for pickup and -1 for drop-off).
Decision Variables
- \(x_{ijk}\): Binary variable, 1 if vehicle \(k\) travels from node \(i\) to node \(j\); 0 otherwise.
- \(s_i\): Service start time at node \(i\).
- \(L_i\): Ride time for user \(i\).
- \(B_{ki}\): Arrival time of vehicle \(k\) at node \(i\).
Objective Function
The objective is to minimize the total travel cost or time: \[ \min \sum_{k \in K} \sum_{i \in P \cup D} \sum_{j \in P \cup D} c_{ij} x_{ijk} \]
Constraints
Vehicle Route: \[ \sum_{j \in P \cup D} x_{ijk} = 1 \quad \forall i \in P, k \in K \] \[ \sum_{i \in P \cup D} x_{ijk} = 1 \quad \forall j \in D, k \in K \]
Vehicle Capacity: \[ \sum_{i \in P} q_i x_{ijk} \leq Q \quad \forall k \in K \]
Time Windows: \[ e_i \leq s_i \leq l_i \quad \forall i \in P \cup D \]
Service Time and Maximum Route Duration: \[ s_i + d_i + t_{ij} \leq s_j \quad \forall i, j \in P \cup D, i \neq j, k \in K B_{ki} + T \geq B_{kj} \quad \forall i, j \in P \cup D, k \in K \]
Pickup and Delivery for the Same Vehicle: \[ \sum_{j \in P \cup D} x_{ijk} = \sum_{j \in P \cup D} x_{jik} \quad \forall i \in P, k \in K \]
Arrival and Ride Time Constraints: \[ B_{ki} + t_{ij} \leq B_{kj} \quad \forall i, j \in P \cup D, k \in K \] \[ L_i \leq L \quad \forall i \in P \cup D \]
4.5 Multi-Objective Optimization
Modern optimization solvers like Gurobi allow for multi-objective optimization, where you can optimize for multiple objectives simultaneously. In Gurobi, you can use the method setObjectiveN to define weighted combinations or priorities among objectives. For example, Listing 4.1 demonstrates how to set up a hierarchical optimization where minimizing total distance is the primary objective and minimizing total delay is the secondary objective. Alternatively, Listing 4.2 shows how to create a weighted sum of the two objectives to find a compromise solution.
# Define weights for each objective
objective_weights = {
OBJ_MINIMIZE_DISTANCE: 0.7,
OBJ_MINIMIZE_TOTAL_DELAY: 0.3
}
# Define the combined objective as a weighted sum of distance and delay
obj_distance = quicksum(
euclidean_dist(i, j) * model.x[k, i, j]
for k in model.K
for i, j in model.A
)
# Define the total delay as the sum of delays at pickup and delivery nodes
obj_delay = quicksum(
model.B[k][i] - model.e[i]
for k in model.K
for i in model.P + model.D
)
# Register each objective with the chosen weights (same priority → weighted sum)
model.setObjectiveN(
obj_distance,
index=0, # Unique index for the objective
priority=0, # Same priority for both objectives to create a weighted sum
weight=objective_weights[OBJ_MINIMIZE_DISTANCE],
name=OBJ_MINIMIZE_DISTANCE,
)
model.setObjectiveN(
obj_delay,
index=1, # Unique index for the objective
priority=0, # Same priority for both objectives to create a weighted sum
weight=objective_weights[OBJ_MINIMIZE_TOTAL_DELAY],
name=OBJ_MINIMIZE_TOTAL_DELAY,
)4.6 Exercise: Update the DARP model to include multi-objective optimization
Listing 4.3 provides a complete implementation of the DARP model using Gurobi. Your task is to update this model to include multi-objective optimization as demonstrated in the previous section.
Base DARP Model
from gurobipy import GRB, quicksum, Model
from collections import defaultdict, OrderedDict
OBJ_MINIMIZE_DISTANCE = "minimize_distance"
OBJ_MINIMIZE_TOTAL_DELAY = "minimize_total_delay"
class ModelDARP:
def __init__(
self,
depot_start,
depot_end,
P,
D,
K,
Q,
d,
q,
e,
l,
dist_func,
obj=OBJ_MINIMIZE_DISTANCE,
):
"""
Initialize the DARP model with input data and define nodes and arcs.
Args:
depot_start (list): List of starting depot nodes.
depot_end (list): List of ending depot nodes.
P (list): List of pickup nodes.
D (list): List of delivery nodes.
K (list): List of vehicles.
Q (dict): Dictionary mapping each vehicle to its capacity.
d (dict): Service duration at each node.
q (dict): Load change at each node.
e (dict): Earliest allowable service time at each node.
l (dict): Latest allowable service time at each node.
dist_func (function): Function that computes distance/travel time between two nodes.
"""
self.obj = obj
self.depot_start = depot_start
self.depot_end = depot_end
self.P = P
self.D = D
self.K = K
self.Q = Q
self.d = d
self.q = q
self.e = e
self.l = l
self.dist_func = dist_func
# Define all nodes: start depot, pickups, deliveries, end depot
self.N = depot_start + P + D + depot_end
# Build the arc set
self.A = []
# Arcs from starting depots to pickup nodes
self.A.extend([(o, p) for o in depot_start for p in P])
# Arcs between pickup and delivery nodes.
# Note: The condition below is intended to exclude arcs from a pickup to its corresponding delivery.
n = len(P)
pd_arcs = [
(i, j)
for i in P + D
for j in P + D
if i != j
and (self.N.index(i) != n + self.N.index(j) if j in P else True)
]
self.A.extend(pd_arcs)
# Arcs from delivery nodes to ending depots
self.A.extend([(d, e) for d in D for e in depot_end])
# Arcs from starting depots directly to ending depots (allows for unused vehicles)
self.A.extend([(o, e) for o in depot_start for e in depot_end])
# Initialize Gurobi model and set a time limit of 60 seconds
self.model = Model("DARP")
self.model.setParam("TimeLimit", 60)
def build(self):
"""Build the optimization model: define variables, objective, and constraints."""
# Decision Variables:
# x[k, i, j]: Binary variable indicating if vehicle k travels from node i to node j.
self.x = {
(k, i, j): self.model.addVar(
vtype=GRB.BINARY, name=f"x_{k}_{i}_{j}"
)
for k in self.K
for i, j in self.A
}
# B[k][i]: Service start time for vehicle k at node i.
self.B = {
k: {
i: self.model.addVar(
lb=self.e[i],
ub=self.l[i],
vtype=GRB.CONTINUOUS,
name=f"B_{k}_{i}",
)
for i in self.N
}
for k in self.K
}
# Q_var[k][i]: Load of vehicle k after visiting node i.
self.Q_var = {
k: {
i: self.model.addVar(
lb=0, ub=self.Q[k], vtype=GRB.CONTINUOUS, name=f"Q_{k}_{i}"
)
for i in self.N
}
for k in self.K
}
if self.obj == OBJ_MINIMIZE_DISTANCE:
# Objective: Minimize total travel distance
self.model.setObjective(
quicksum(
self.dist_func(i, j) * self.x[k, i, j]
for k in self.K
for i, j in self.A
),
GRB.MINIMIZE,
)
elif self.obj == OBJ_MINIMIZE_TOTAL_DELAY:
# Objective: Minimize total delay
self.model.setObjective(
quicksum(
self.B[k][i] - self.e[i] for k in self.K for i in self.P + self.D
),
GRB.MINIMIZE,
)
else:
raise ValueError("Invalid objective function specified.")
# 1. Each pickup and delivery node must be visited exactly once.
for i in self.P + self.D:
self.model.addConstr(
quicksum(
self.x[k, i, j]
for k in self.K
for j in self.N
if (i, j) in self.A
)
== 1,
name=f"visit_{i}",
)
# 2. Ensure each vehicle starts at a depot_start and ends at a depot_end.
for k in self.K:
self.model.addConstr(
quicksum(
self.x[k, o, j]
for o in self.depot_start
for j in self.N
if (o, j) in self.A
)
== 1,
name=f"start_{k}",
)
self.model.addConstr(
quicksum(
self.x[k, i, d]
for d in self.depot_end
for i in self.N
if (i, d) in self.A
)
== 1,
name=f"end_{k}",
)
# 3. Flow conservation: For each vehicle, the number of arrivals equals departures at each pickup/delivery node.
for k in self.K:
for i in self.P + self.D:
self.model.addConstr(
quicksum(
self.x[k, j, i] for j in self.N if (j, i) in self.A
)
== quicksum(
self.x[k, i, j] for j in self.N if (i, j) in self.A
),
name=f"flow_{k}_{i}",
)
# 4. Time feasibility: Respect time windows and travel times using a Big-M formulation.
for k in self.K:
for i, j in self.A:
M = self.l[i] + self.d[i] + self.dist_func(i, j) - self.e[j]
self.model.addConstr(
self.B[k][j]
>= self.B[k][i]
+ self.d[i]
+ self.dist_func(i, j)
- M * (1 - self.x[k, i, j]),
name=f"time_{k}_{i}_{j}",
)
# 5. Load feasibility: Ensure capacity constraints are not violated.
for k in self.K:
for i, j in self.A:
M = self.Q[k] + max(0, self.q[j])
self.model.addConstr(
self.Q_var[k][j]
>= self.Q_var[k][i]
+ self.q[j]
- M * (1 - self.x[k, i, j]),
name=f"load_{k}_{i}_{j}",
)
# 5.1 Load feasibility: Start with 0 load at the depot
for k in self.K:
self.model.addConstr(self.Q_var[k][self.depot_start[0]] == 0)
# 5.2 Load feasibility: End with 0 load at the depot
for k in self.K:
self.model.addConstr(self.Q_var[k][self.depot_end[0]] == 0)
# 6. Precedence: For each request, the pickup must occur before its corresponding delivery.
for idx, p in enumerate(self.P):
d = self.D[idx] # Assumes P[i] corresponds to D[i]
for k in self.K:
self.model.addConstr(
self.B[k][d]
>= self.B[k][p] + self.d[p] + self.dist_func(p, d),
name=f"precedence_{k}_{p}_{d}",
)
def get_flow_edges(self):
"""
Retrieve all arcs (edges) with x variable value close to 1.
Returns:
List of tuples (k, i, j) representing used arcs.
"""
edges = []
for k in self.K:
for i, j in self.A:
if self.x[k, i, j].X > 0.9:
edges.append((k, i, j))
return edges
def get_dict_route_vehicle(self, edges):
"""
Construct a route for each vehicle based on the selected arcs.
Args:
edges (list): List of arcs (k, i, j) used in the solution.
Returns:
Dictionary mapping each vehicle to its route (ordered list of nodes).
"""
vehicle_arcs = defaultdict(dict)
vehicle_origin = {}
# Build a mapping for each vehicle: from node i to its next node j.
for k, i, j in edges:
vehicle_arcs[k][i] = j
if i in self.depot_start:
vehicle_origin[k] = i
# Construct each vehicle's route by following the arcs from the origin.
routes = {}
for k, arc in vehicle_arcs.items():
current = vehicle_origin[k]
route = []
while current in arc:
route.append(current)
current = arc[current]
route.append(current) # Append the final node (ending depot)
routes[k] = route
return routes
def get_vehicle_routes_dict(self):
"""Helper method to obtain the vehicle routes dictionary from the flow edges."""
return self.get_dict_route_vehicle(self.get_flow_edges())
def get_solution(self):
"""
Process the solution to extract performance metrics and detailed route information.
Returns:
summary (dict): Summary metrics for the overall solution.
fleet_solution (dict): Detailed route and timing info per vehicle.
"""
total_cost = total_duration = 0
fleet_solution = {}
vehicle_routes = self.get_vehicle_routes_dict()
serviced_set = set()
# Process each vehicle's route
for k in self.K:
route_ids = vehicle_routes[k]
# Record serviced pickup nodes for summary statistics
serviced_vehicle = set(route_ids).intersection(self.P)
serviced_set.update(serviced_vehicle)
route_data = OrderedDict()
k_total_cost = k_total_distance = k_max_load = 0
arrival = 0
# Calculate route metrics over consecutive edges
edges = list(zip(route_ids[:-1], route_ids[1:]))
for i, j in edges:
travel_time = self.dist_func(i, j)
k_total_cost += travel_time
k_total_distance += travel_time
arrival = self.B[k][i].X + self.d[i] + travel_time
k_max_load = max(k_max_load, self.Q_var[k][i].X)
# Record node-specific information
route_data[i] = {
"id": i,
"arrival_time": self.B[k][i].X,
"load": self.Q_var[k][i].X,
}
# Process the final depot node
final_depot = route_ids[-1]
route_data[final_depot] = {
"id": final_depot,
"arrival_time": self.B[k][final_depot].X,
"load": self.Q_var[k][final_depot].X,
}
duration = (
route_data[final_depot]["arrival_time"]
- route_data[route_ids[0]]["arrival_time"]
)
total_duration += duration
total_cost += k_total_cost
fleet_solution[k] = {
"id": k,
"D": k_total_cost,
"Q": k_max_load,
"route": list(route_data.values()),
}
total_latency = sum(
n["arrival_time"]
for sol in fleet_solution.values()
for n in sol["route"]
if n["id"] in self.P or n["id"] in self.D
)
summary = {
"total_distance": total_cost,
"total_duration": total_duration,
"total_latency": total_latency,
"n_serviced": len(serviced_set),
}
return summary, fleet_solution
def solve(self):
"""Solve the optimization model and print the solution summary."""
self.model.optimize()
if self.model.status == GRB.OPTIMAL:
summary, fleet_solution = self.get_solution()
print("Optimal solution found!")
return {"summary": summary, "fleet_solution": fleet_solution}
else:
print("No optimal solution found.")
return NoneData Setup
Listing 4.4 defines the basic data, such as nodes, locations, vehicle capacities, service durations, and time windows. We also define the Euclidean distance function.
# Import necessary libraries
import math
import pandas as pd
# Import the DARP model and objective constants from the darp module
# from darp import ModelDARP, OBJ_MINIMIZE_DISTANCE, OBJ_MINIMIZE_TOTAL_DELAY
from pprint import pprint
def to_df(sol, model=None):
"""Convert the route solution dictionary into a tabular DataFrame."""
if not sol:
return pd.DataFrame()
rows = []
fleet_solution = sol.get("fleet_solution", {})
for vehicle_id, vehicle in fleet_solution.items():
route = vehicle.get("route", [])
for stop_order, node in enumerate(route):
rows.append(
{
"vehicle": vehicle_id,
"stop_order": stop_order,
"node_id": node.get("id"),
"arrival_time": node.get("arrival_time"),
"load": node.get("load"),
"vehicle_distance": vehicle.get("D"),
"vehicle_max_load": vehicle.get("Q"),
}
)
df = pd.DataFrame(rows)
if not df.empty:
df = df.sort_values(["vehicle", "stop_order"]).reset_index(drop=True)
return df
# Define depot nodes (starting and ending points for vehicles)
depot_start = ["Depot_Start"]
depot_end = ["Depot_End"]
# Define pickup nodes (e.g., P1, P2)
P = ["P1", "P2"]
# Define delivery nodes (each pickup has a corresponding delivery: P1 -> D1, P2 -> D2)
D = ["D1", "D2"]
# Define the locations for all nodes as (x, y) coordinates
locations = {
"Depot_Start": (0, 0),
"Depot_End": (0, 0),
"P1": (10, 0),
"P2": (20, 0),
"D1": (30, 0),
"D2": (40, 0)
}
# Define the fleet: here we have a single vehicle (id = 1)
K = ["V1"]
# Set the capacity for the vehicle (here, capacity is 10 units)
Q = {"V1": 10}
# Define service durations at each node
d = {node: 0 for node in depot_start + depot_end + P + D}
# Define loads
q = {
"Depot_Start": 0,
"Depot_End": 0,
"P1": 5,
"P2": 5,
"D1": -5,
"D2": -5
}
# Define time windows for service at each node
e = {node: 0 for node in depot_start + depot_end + P + D} # Earliest service times
l = {node: 80 for node in depot_start + depot_end + P + D} # Latest service times
# Define the distance function using Euclidean distance
def euclidean_dist(i, j):
"""
Calculate Euclidean distance between two nodes i and j.
Parameters:
i, j: Node identifiers.
Returns:
The Euclidean distance based on (x, y) coordinates.
"""
return math.sqrt(
(locations[i][0] - locations[j][0]) ** 2 +
(locations[i][1] - locations[j][1]) ** 2
)Single Objective: Minimize Distance
Listing 4.5 section demonstrates creating a DARP model instance with the objective of minimizing total travel distance. We then build and solve the model.
# Create a DARP model instance with the objective to minimize total travel distance.
model = ModelDARP(
depot_start, depot_end, P, D, K, Q, d, q, e, l,
euclidean_dist,
obj=OBJ_MINIMIZE_DISTANCE
)
# Build the internal optimization model (defining decision variables and constraints)
model.build()
# Solve the model using Gurobi
sol = model.solve()
# Print the solution
pprint(sol)
# Show the solution as a DataFrame
df_min_distance = to_df(sol, model)
df_min_distanceSet parameter Username
Set parameter LicenseID to value 2777413
Academic license - for non-commercial use only - expires 2027-02-10
Set parameter TimeLimit to value 60
Gurobi Optimizer version 13.0.1 build v13.0.1rc0 (win64 - Windows 11+.0 (26200.2))
CPU model: Intel(R) Core(TM) Ultra 7 155H, instruction set [SSE2|AVX|AVX2]
Thread count: 16 physical cores, 22 logical processors, using up to 22 threads
Non-default parameters:
TimeLimit 60
Optimize a model with 44 rows, 27 columns and 138 nonzeros (Min)
Model fingerprint: 0x5de98592
Model has 14 linear objective coefficients
Variable types: 12 continuous, 15 integer (15 binary)
Coefficient statistics:
Matrix range [1e+00, 1e+02]
Objective range [1e+01, 4e+01]
Bounds range [1e+00, 8e+01]
RHS range [1e+00, 8e+01]
Found heuristic solution: objective 80.0000000
Presolve removed 44 rows and 27 columns
Presolve time: 0.00s
Presolve: All rows and columns removed
Explored 0 nodes (0 simplex iterations) in 0.02 seconds (0.00 work units)
Thread count was 1 (of 22 available processors)
Solution count 1: 80
Optimal solution found (tolerance 1.00e-04)
Best objective 8.000000000000e+01, best bound 8.000000000000e+01, gap 0.0000%
Optimal solution found!
{'fleet_solution': {'V1': {'D': 80.0,
'Q': 10.0,
'id': 'V1',
'route': [{'arrival_time': 0.0,
'id': 'Depot_Start',
'load': 0.0},
{'arrival_time': 10.0,
'id': 'P1',
'load': 5.0},
{'arrival_time': 20.0,
'id': 'P2',
'load': 10.0},
{'arrival_time': 40.0,
'id': 'D2',
'load': 5.0},
{'arrival_time': 50.0,
'id': 'D1',
'load': 0.0},
{'arrival_time': 80.0,
'id': 'Depot_End',
'load': 0.0}]}},
'summary': {'n_serviced': 2,
'total_distance': 80.0,
'total_duration': 80.0,
'total_latency': 120.0}}| vehicle | stop_order | node_id | arrival_time | load | vehicle_distance | vehicle_max_load | |
|---|---|---|---|---|---|---|---|
| 0 | V1 | 0 | Depot_Start | 0.0 | 0.0 | 80.0 | 10.0 |
| 1 | V1 | 1 | P1 | 10.0 | 5.0 | 80.0 | 10.0 |
| 2 | V1 | 2 | P2 | 20.0 | 10.0 | 80.0 | 10.0 |
| 3 | V1 | 3 | D2 | 40.0 | 5.0 | 80.0 | 10.0 |
| 4 | V1 | 4 | D1 | 50.0 | 0.0 | 80.0 | 10.0 |
| 5 | V1 | 5 | Depot_End | 80.0 | 0.0 | 80.0 | 10.0 |
Single Objective: Minimize Total Delay
Listing 4.6 section demonstrates creating a DARP model instance with the objective of minimizing total delay. We then build and solve the model.
# Create a new DARP model instance with the objective to minimize total delay
model = ModelDARP(
depot_start, depot_end, P, D, K, Q, d, q, e, l,
euclidean_dist,
obj=OBJ_MINIMIZE_TOTAL_DELAY
)
# Build and solve the model
model.build()
# Solve the model using Gurobi
sol = model.solve()
# Print the solution
pprint(sol)
# Show the solution as a DataFrame
df_min_delay = to_df(sol, model)
df_min_delaySet parameter TimeLimit to value 60
Gurobi Optimizer version 13.0.1 build v13.0.1rc0 (win64 - Windows 11+.0 (26200.2))
CPU model: Intel(R) Core(TM) Ultra 7 155H, instruction set [SSE2|AVX|AVX2]
Thread count: 16 physical cores, 22 logical processors, using up to 22 threads
Non-default parameters:
TimeLimit 60
Optimize a model with 44 rows, 27 columns and 138 nonzeros (Min)
Model fingerprint: 0xd62f3e7e
Model has 4 linear objective coefficients
Variable types: 12 continuous, 15 integer (15 binary)
Coefficient statistics:
Matrix range [1e+00, 1e+02]
Objective range [1e+00, 1e+00]
Bounds range [1e+00, 8e+01]
RHS range [1e+00, 8e+01]
Found heuristic solution: objective 120.0000000
Presolve removed 44 rows and 27 columns
Presolve time: 0.00s
Presolve: All rows and columns removed
Explored 0 nodes (0 simplex iterations) in 0.01 seconds (0.00 work units)
Thread count was 1 (of 22 available processors)
Solution count 2: 100 120
Optimal solution found (tolerance 1.00e-04)
Best objective 1.000000000000e+02, best bound 1.000000000000e+02, gap 0.0000%
Optimal solution found!
{'fleet_solution': {'V1': {'D': 80.0,
'Q': 10.0,
'id': 'V1',
'route': [{'arrival_time': 0.0,
'id': 'Depot_Start',
'load': 0.0},
{'arrival_time': 10.0,
'id': 'P1',
'load': 5.0},
{'arrival_time': 20.0,
'id': 'P2',
'load': 10.0},
{'arrival_time': 30.0,
'id': 'D1',
'load': 5.0},
{'arrival_time': 40.0,
'id': 'D2',
'load': 0.0},
{'arrival_time': 80.0,
'id': 'Depot_End',
'load': 0.0}]}},
'summary': {'n_serviced': 2,
'total_distance': 80.0,
'total_duration': 80.0,
'total_latency': 100.0}}| vehicle | stop_order | node_id | arrival_time | load | vehicle_distance | vehicle_max_load | |
|---|---|---|---|---|---|---|---|
| 0 | V1 | 0 | Depot_Start | 0.0 | 0.0 | 80.0 | 10.0 |
| 1 | V1 | 1 | P1 | 10.0 | 5.0 | 80.0 | 10.0 |
| 2 | V1 | 2 | P2 | 20.0 | 10.0 | 80.0 | 10.0 |
| 3 | V1 | 3 | D1 | 30.0 | 5.0 | 80.0 | 10.0 |
| 4 | V1 | 4 | D2 | 40.0 | 0.0 | 80.0 | 10.0 |
| 5 | V1 | 5 | Depot_End | 80.0 | 0.0 | 80.0 | 10.0 |
4.7 Exercises: Multi-Objective Optimization for the DARP
Task 1: Combine Objectives Linearly
Create a new DARP model instance with the objective to minimize a linear combination of total distance and total delay. Choose weights for each objective and solve the model. Create a toy example that clearly shows the trade-off between the two objectives.
Task 2: Hierarchical Optimization
Implement a hierarchical optimization approach where you first minimize total delay and then minimize total distance. Create a toy example to clearly showcase your approach is working.
Task 3: Goal Programming
Implement a goal programming approach where you set a target for passenger delay (e.g., no more than 30 minutes) and minimize total distance while ensuring the delay target is met. Create a toy example that the goal programming approach can solve effectively, and compare it to the previous approaches.
Task 4: Pareto Frontier Exploration
Propose a toy instance of the DARP that allows you to plot all the solutions on the Pareto frontier for the two objectives (minimizing total distance and minimizing total delay). Solve the model for different weight combinations and plot the resulting solutions to visualize the trade-offs between the objectives. (Tip: consider integer time and distance units to decrease the solution space and make visualization easier.)