“目的是匹配乘客和司机，满足车辆容量和个人行程限制，同时最大限度地减少总行驶距离。司机和乘客在协商具体的上下车地点方面有一定的灵活性，因此初步安排行程在较小的一组标准位置上，代表小镇、地区或道路网络中的主要路口。因此，许多用户可能共享相同的出发地或目的地。我们假设所有位置对之间的旅行时间已知，并且我们假设所有驾驶员将在给定的对之间使用相同的路线。同样，我们假设时间窗口基于标准间隔，例如 15 分钟，用户将在该粒度上指定他们的最晚到达时间。司机的行程报价被指定为从开始到结束的路线，最早出发和最晚到达的时间窗口，以及可供乘客使用的座位数。骑手的出行请求指定了出发地点目的地和时间窗口。我们假设司机会开车，无论是否匹配；没有获得匹配的骑手可以在给定的概率下在系统之外自行驾驶，否则他们将乘坐公共交通工具。分配一名或多名乘客的每位司机必须获得路线上每个点的出发时间和到达时间，以便任何一对位置之间的时间间隔不小于已知的行程时间。对于将骑手分配给司机的情况，骑手的起点和终点位置必须按正确的顺序位于司机的路线上，并且司机的时间必须满足骑手的时间窗口。只要路线上各个地点之间行驶的乘客数量不超过可用座位数，就可以将多名乘客分配给同一位司机。当至少一名乘客被分配到司机的行程时，就会为司机提供服务；当乘客被分配到某个行程时，他或她就会得到服务。拼车问题的一个解决方案是为满足上述约束的乘客分配匹配的司机。最佳解决方案可最大限度地减少总行驶距离，即驾驶员与固定比例未得到服务的乘客的路线距离之和”
我尝试使用 PuLP 在 Python 中编写此问题的代码。问题是离线的，我们在工作开始之前就有乘客和司机的参数。我想用这段代码将它们相互匹配：
from pulp import *
import networkx as nx
import matplotlib.pyplot as plt
D = ['driver1', 'driver2']
R = ['rider1', 'rider2', 'rider3','rider4','rider5']
V = ['location1', 'location2', 'location3', 'location4', 'location5', 'location6', 'location7']
G = nx.DiGraph()
edges = {
('location1', 'location2'): 10,
('location2', 'location3'): 12,
('location3', 'location4'): 15,
('location4', 'location2'): 10,
('location6', 'location5'): 10,
('location1', 'location5'): 10,
('location4', 'location1'): 10,
('location5', 'location6'): 10,
('location1', 'location4'): 10,
('location2', 'location5'): 10,
('location1', 'location6'): 10,
('location4', 'location5'): 10,
('location5', 'location3'): 20,
('location1', 'location6'): 50,
('location5', 'location7'): 10,
('location5', 'location2'): 5,
('location7', 'location3'): 5
}
G.add_weighted_edges_from((u, v, w) for (u, v), w in edges.items())
vsr = {'rider1': 'location1', 'rider2': 'location2', 'rider3': 'location3', 'rider4': 'location2', 'rider5': 'location5'}
ver = {'rider1': 'location4', 'rider2': 'location5', 'rider3': 'location6', 'rider4': 'location5', 'rider5': 'location7'}
num_people = {'rider1': 1, 'rider2': 2, 'rider3': 1 ,'rider4': 2,'rider5':1}
πd = {'driver1': ['location1', 'location2', 'location3', 'location4', 'location5', 'location6'],
'driver2': ['location2', 'location3', 'location4', 'location1', 'location5', 'location7']}
pos = nx.spring_layout(G)
nx.draw(G, pos, with_labels=True, node_color='lightblue', node_size=1500)
labels = nx.get_edge_attributes(G, 'weight')
nx.draw_networkx_edge_labels(G, pos, edge_labels=labels)
shortest_paths = dict(nx.all_pairs_dijkstra_path(G))
shortest_path_lengths = dict(nx.all_pairs_dijkstra_path_length(G))
stv_v_prime = {}
dv_v_prime = {}
for v, lengths in shortest_path_lengths.items():
for v_prime, length in lengths.items():
dv_v_prime[(v, v_prime)] = length
for v, lengths in shortest_path_lengths.items():
for v_prime, length in lengths.items():
stv_v_prime[(v, v_prime)] = (length * 5) / 60
dvsr_ver = {}
for rider in R:
start_location = vsr[rider]
end_location = ver[rider]
shortest_distance = dv_v_prime[(start_location, end_location)]
dvsr_ver[rider] = {'shortest_distance': shortest_distance}
for rider, location in vsr.items():
plt.text(pos[location][0], pos[location][1]+0.1, f"{rider} start", horizontalalignment='center', color='green')
for rider, location in ver.items():
plt.text(pos[location][0], pos[location][1]-0.1, f"{rider} end", horizontalalignment='center', color='red')
for driver, path in πd.items():
nx.draw_networkx_edges(G, pos, edgelist=[(path[i], path[i+1]) for i in range(len(path)-1)], edge_color='yellow', width=2)
#plt.show()
etd={'driver1': 8, 'driver2': 8}
ltd={'driver1': 24, 'driver2': 24}
qd = {'driver1': 4, 'driver2': 4}
etr = {'rider1': 8, 'rider2': 8, 'rider3': 8, 'rider4':8,'rider5':9}
ltr = {'rider1': 24, 'rider2': 24, 'rider3': 24, 'rider4':24,'rider5':24}
M = 1000
startsπd_v = {d: {v: [] for v in V} for d in D}
endsπd_v = {d: {v: [] for v in V} for d in D}
for d in D:
for r in R:
if vsr[r] in πd[d]:
startsπd_v[d][vsr[r]].append(r)
if ver[r] in πd[d]:
endsπd_v[d][ver[r]].append(r)
predπd_v = {}
for d in πd:
predπd_v[d] = []
for i in range(1, len(πd[d])):
predπd_v[d].append(πd[d][i-1])
default_distance = 0
prob = LpProblem("Ride_Sharing_Problem", LpMinimize)
#Decision Variables
yd_r = LpVariable.dicts("match", ((d, r) for d in D for r in R), 0, 1, LpBinary)
td_v = LpVariable.dicts("departure_time", ((d, v) for d in D for v in V), etd, ltd, LpContinuous)
#Auxiliary Variables
z_r = LpVariable.dicts("served_rider", (r for r in R), 0, 1, LpBinary)
od_v = LpVariable.dicts("car_occupancy", ((d, v) for d in D for v in V), 0, None, LpInteger)
#Our objective is to minimize:
prob += lpSum([yd_r[d, r] * dvsr_ver[r].get('shortest_distance', default_distance) for d in D ]) + lpSum((1 - z_r[r]) * dvsr_ver[r].get('shortest_distance', default_distance) for r in R)
for d in D:
for r in R:
if vsr[r] not in πd[d] or ver[r] not in πd[d]:
prob += yd_r[d, r] == 0
for d in D:
for r in R:
prob += lpSum(yd_r[d, r] for r in R if etr[r] < etd[d] or ltr[r] > ltd[d]) == 0
for r in R:
prob += lpSum(yd_r[d, r] for d in D) <= 1
for r in R:
prob += lpSum(yd_r[d, r] for d in D) == z_r[r]
for r in R:
prob += z_r[r] >= yd_r['driver1', r] + yd_r['driver2', r] - 1
prob += z_r[r] <= yd_r['driver1', r]
prob += z_r[r] <= yd_r['driver2', r]
prob += lpSum(yd_r[d, r] for d in D) >= z_r[r]
for d in D:
for v in V:
prob += od_v[d, v] <= qd[d]
for d in D:
prob += lpSum(yd_r[d, r] * num_people[r] for r in R) <= qd[d]
for d in D:
for v in V:
if v in predπd_v:
prob += od_v[d, v] == od_v[d, predπd_v[v]] + lpSum(yd_r[d, r] * num_people[r] for r in startsπd_v[v]) - lpSum(yd_r[d, r] * num_people[r] for r in endsπd_v[v])
for r in R:
if d == r:
prob += yd_r[d, r] * etr[r] <= td_v[d, vsr[r]]
prob += M - td_v[d, ver[r]] >= (M - ltr[r]) * yd_r[d, r]
time_window = 1
for d in D:
for v in V:
if v in predπd_v:
prob += td_v[d, v] >= td_v[d, predπd_v[v]] + stv_v_prime[(predπd_v[v], v)]
for d in D:
for r in R:
for v in V:
for v_prime in V:
if v != v_prime:
match = int(vsr[r] == v and ver[r] == v_prime)
prob += match * yd_r[d, r] - time_window <= td_v[d, v] - td_v[d, v_prime]
prob += match * yd_r[d, r] + time_window >= td_v[d, v] - td_v[d, v_prime]
for d in D:
for i in range(len(πd[d])-1):
prob += td_v[d, πd[d][i+1]] >= td_v[d, πd[d][i]] + stv_v_prime[(πd[d][i], πd[d][i+1])]
prob.solve()
for v in prob.variables():
#print(v.name, "=", v.varValue)
#print("Objective:", value(model.objective))
print("Objective:", value(prob.objective))
但是我无法确定这个错误的错误：
TypeError: must be real number, not dict
正如我在评论中所写，第一个主要问题是，在
prob += lpSumrfor r in R下一个问题是您尝试将整个字典
etdltd不要散布图形和业务逻辑。我已经注释掉了图表。如果您想重新引入它，请在不同的函数中执行它。
以下内容修复了这些问题，进行了大量的命名空间清理，并将问题解决到执行的地步（并由于不可行而失败）。
from typing import NamedTuple
import pulp
import networkx
# import matplotlib.pyplot as plt
class NetworkVars(NamedTuple):
drivers: tuple[str, ...]
riders: tuple[str, ...]
locations: tuple[str, ...]
num_people: dict[str, int]
vsr: dict[str, str]
ver: dict[str, str]
etr: dict[str, int]
etd: dict[str, int]
ltr: dict[str, int]
ltd: dict[str, int]
qd: dict[str, int]
πd: dict[str, list[str]]
predπd_v: dict[str, list[str]]
startsπd_v: dict[str, dict[str, list[str]]]
endsπd_v: dict[str, dict[str, list[str]]]
stv_v_prime: dict[tuple[str, str], float]
dvsr_ver: dict[str, dict[str, int]]
@classmethod
def default(cls) -> 'NetworkVars':
drivers = ('driver1', 'driver2')
riders = ('rider1', 'rider2', 'rider3', 'rider4', 'rider5')
locations = ('location1', 'location2', 'location3', 'location4', 'location5', 'location6', 'location7')
graph = networkx.DiGraph()
edges = {
('location1', 'location2'): 10,
('location2', 'location3'): 12,
('location3', 'location4'): 15,
('location4', 'location2'): 10,
('location6', 'location5'): 10,
('location1', 'location5'): 10,
('location4', 'location1'): 10,
('location5', 'location6'): 10,
('location1', 'location4'): 10,
('location2', 'location5'): 10,
('location1', 'location6'): 10,
('location4', 'location5'): 10,
('location5', 'location3'): 20,
('location1', 'location6'): 50,
('location5', 'location7'): 10,
('location5', 'location2'): 5,
('location7', 'location3'): 5,
}
graph.add_weighted_edges_from((u, v, w) for (u, v), w in edges.items())
vsr = {'rider1': 'location1', 'rider2': 'location2', 'rider3': 'location3', 'rider4': 'location2',
'rider5': 'location5'}
ver = {'rider1': 'location4', 'rider2': 'location5', 'rider3': 'location6', 'rider4': 'location5',
'rider5': 'location7'}
num_people = {'rider1': 1, 'rider2': 2, 'rider3': 1, 'rider4': 2, 'rider5': 1}
πd = {'driver1': ['location1', 'location2', 'location3', 'location4', 'location5', 'location6'],
'driver2': ['location2', 'location3', 'location4', 'location1', 'location5', 'location7']}
# pos = networkx.spring_layout(G=graph)
# networkx.draw(G=graph, pos=pos, with_labels=True, node_color='lightblue', node_size=1500)
# labels = networkx.get_edge_attributes(G=graph, name='weight')
# networkx.draw_networkx_edge_labels(G=graph, pos=pos, edge_labels=labels)
# shortest_paths = dict(networkx.all_pairs_dijkstra_path(G=graph))
shortest_path_lengths: dict[str, dict[str, int]] = dict(
networkx.all_pairs_dijkstra_path_length(G=graph)
)
stv_v_prime = {}
dv_v_prime = {}
for v, lengths in shortest_path_lengths.items():
for v_prime, length in lengths.items():
dv_v_prime[(v, v_prime)] = length
for v, lengths in shortest_path_lengths.items():
for v_prime, length in lengths.items():
stv_v_prime[(v, v_prime)] = length * 5 / 60
dvsr_ver = {}
for rider in riders:
start_location = vsr[rider]
end_location = ver[rider]
shortest_distance = dv_v_prime[(start_location, end_location)]
dvsr_ver[rider] = {'shortest_distance': shortest_distance}
# for rider, location in vsr.items():
# plt.text(pos[location][0], pos[location][1] + 0.1, f"{rider} start", horizontalalignment='center', color='green')
# for rider, location in ver.items():
# plt.text(pos[location][0], pos[location][1] - 0.1, f"{rider} end", horizontalalignment='center', color='red')
# for driver, path in πd.items():
# networkx.draw_networkx_edges(
# G=graph, pos=pos,
# edgelist=[(path[i], path[i + 1]) for i in range(len(path) - 1)],
# edge_color='yellow',
# width=2,
# )
# plt.show()
etd = {'driver1': 8, 'driver2': 8}
ltd = {'driver1': 24, 'driver2': 24}
qd = {'driver1': 4, 'driver2': 4}
etr = {'rider1': 8, 'rider2': 8, 'rider3': 8, 'rider4': 8, 'rider5': 9}
ltr = {'rider1': 24, 'rider2': 24, 'rider3': 24, 'rider4': 24, 'rider5': 24}
startsπd_v = {d: {v: [] for v in locations} for d in drivers}
endsπd_v = {d: {v: [] for v in locations} for d in drivers}
for d in drivers:
for r in riders:
if vsr[r] in πd[d]:
startsπd_v[d][vsr[r]].append(r)
if ver[r] in πd[d]:
endsπd_v[d][ver[r]].append(r)
predπd_v = {}
for d in πd:
predπd_v[d] = []
for i in range(1, len(πd[d])):
predπd_v[d].append(πd[d][i - 1])
return cls(
drivers=drivers, riders=riders, locations=locations, num_people=num_people,
vsr=vsr, ver=ver, etr=etr, etd=etd, ltr=ltr, ltd=ltd,
predπd_v=predπd_v, startsπd_v=startsπd_v, endsπd_v=endsπd_v,
stv_v_prime=stv_v_prime, qd=qd, πd=πd, dvsr_ver=dvsr_ver,
)
def make_lp_vars(network: NetworkVars) -> tuple[
pulp.LpProblem, # prob
dict[tuple[str, str], pulp.LpVariable], # yd_r
dict[str, pulp.LpVariable], # z_r
dict[tuple[str, str], pulp.LpVariable], # od_v
dict[tuple[str, str], pulp.LpVariable], # td_v
]:
prob = pulp.LpProblem(name="Ride_Sharing", sense=pulp.LpMinimize)
# Decision Variables
yd_r = pulp.LpVariable.dicts(
name="match",
indices=((d, r) for d in network.drivers for r in network.riders),
cat=pulp.LpBinary,
)
td_v = {
(d, v): pulp.LpVariable(
name=f"departure_time_{(d, v)}",
lowBound=network.etd[d], upBound=network.ltd[d],
cat=pulp.LpContinuous,
)
for d in network.drivers
for v in network.locations
}
# Auxiliary Variables
z_r = pulp.LpVariable.dicts(
name="served_rider",
indices=list(network.riders),
cat=pulp.LpBinary,
)
od_v = pulp.LpVariable.dicts(
name="car_occupancy",
indices=((d, v) for d in network.drivers for v in network.locations),
lowBound=0, upBound=None, cat=pulp.LpInteger,
)
return prob, yd_r, z_r, od_v, td_v
def set_objective(
network: NetworkVars,
prob: pulp.LpProblem,
yd_r: dict[tuple[str, str], pulp.LpVariable],
z_r: dict[str, pulp.LpVariable],
default_distance: int = 0,
) -> None:
# Our objective is to minimize:
prob.setObjective(
pulp.lpSum([
yd_r[d, r] * network.dvsr_ver[r].get('shortest_distance', default_distance)
for d in network.drivers
for r in network.riders
]) + pulp.lpSum(
(1 - z_r[r]) * network.dvsr_ver[r].get('shortest_distance', default_distance)
for r in network.riders
)
)
def set_constraints(
net: NetworkVars,
prob: pulp.LpProblem,
yd_r: dict[tuple[str, str], pulp.LpVariable],
z_r: dict[str, pulp.LpVariable],
od_v: dict[tuple[str, str], pulp.LpVariable],
td_v: dict[tuple[str, str], pulp.LpVariable],
M: int,
):
for d in net.drivers:
for r in net.riders:
if net.vsr[r] not in net.πd[d] or net.ver[r] not in net.πd[d]:
prob += yd_r[d, r] == 0
for d in net.drivers:
prob += pulp.lpSum(
yd_r[d, r]
for r in net.riders
if net.etr[r] < net.etd[d] or net.ltr[r] > net.ltd[d]
) == 0
for r in net.riders:
prob += pulp.lpSum(yd_r[d, r] for d in net.drivers) <= 1
for r in net.riders:
prob += pulp.lpSum(yd_r[d, r] for d in net.drivers) == z_r[r]
for r in net.riders:
prob += z_r[r] >= yd_r['driver1', r] + yd_r['driver2', r] - 1
prob += z_r[r] <= yd_r['driver1', r]
prob += z_r[r] <= yd_r['driver2', r]
prob += pulp.lpSum(yd_r[d, r] for d in net.drivers) >= z_r[r]
for d in net.drivers:
for v in net.locations:
prob += od_v[d, v] <= net.qd[d]
for d in net.drivers:
prob += pulp.lpSum(yd_r[d, r] * net.num_people[r] for r in net.riders) <= net.qd[d]
for d in net.drivers:
for v in net.locations:
if v in net.predπd_v:
prob += od_v[d, v] == od_v[d, net.predπd_v[v]] + pulp.lpSum(
yd_r[d, r] * net.num_people[r] for r in net.startsπd_v[v]) - pulp.lpSum(
yd_r[d, r] * net.num_people[r] for r in net.endsπd_v[v])
for r in net.riders:
if d == r:
prob += yd_r[d, r] * net.etr[r] <= td_v[d, net.vsr[r]]
prob += M - td_v[d, net.ver[r]] >= (M - net.ltr[r]) * yd_r[d, r]
time_window = 1
for d in net.drivers:
for v in net.locations:
if v in net.predπd_v:
prob += td_v[d, v] >= td_v[d, net.predπd_v[v]] + net.stv_v_prime[(net.predπd_v[v], v)]
for d in net.drivers:
for r in net.riders:
for v in net.locations:
for v_prime in net.locations:
if v != v_prime:
match = int(net.vsr[r] == v and net.ver[r] == v_prime)
prob += match * yd_r[d, r] - time_window <= td_v[d, v] - td_v[d, v_prime]
prob += match * yd_r[d, r] + time_window >= td_v[d, v] - td_v[d, v_prime]
for d in net.drivers:
for i in range(len(net.πd[d]) - 1):
prob += td_v[d, net.πd[d][i + 1]] >= td_v[d, net.πd[d][i]] + net.stv_v_prime[(net.πd[d][i], net.πd[d][i + 1])]
def solve(prob: pulp.LpProblem) -> None:
prob.solve()
# for v in prob.variables():
# print(v.name, "=", v.varValue)
# print("Objective:", value(model.objective))
print("Objective:", pulp.value(prob.objective))
def main() -> None:
network = NetworkVars.default()
prob, yd_r, z_r, od_v, td_v = make_lp_vars(network)
set_objective(
network=network, prob=prob, yd_r=yd_r, z_r=z_r, default_distance=0,
)
set_constraints(
net=network, prob=prob,
yd_r=yd_r, z_r=z_r, od_v=od_v, td_v=td_v,
M=1000,
)
solve(prob=prob)
if __name__ == '__main__':
main()
At line 2 NAME MODEL
At line 3 ROWS
At line 905 COLUMNS
At line 2800 RHS
At line 3701 BOUNDS
At line 3759 ENDATA
Problem MODEL has 900 rows, 43 columns and 1821 elements
Coin0008I MODEL read with 0 errors
Option for timeMode changed from cpu to elapsed
Problem is infeasible - 0.00 seconds
Option for printingOptions changed from normal to all
Total time (CPU seconds): 0.00 (Wallclock seconds): 0.00