本文为本人博客《一种无人机配合卡车配送的车辆路径规划模型》的代码分享。
由于近期此文的关注者较多，代码分享较为不便，因此决定专门写一篇博客以提供源码。
感谢各位博友关注，本人能力有限，如有错误，还请及时批评指正！
原文链接：https://blog.csdn.net/Zhang_0702_China/article/details/115215219
代码文件结构
代码的文件结构如下：
- config: 参数、输入数据（随机生成）
- docs: 模型文档、参考文献（见前面原文链接）
- log: 运行日志
- model: 模型核心模块
- output: 输出文件，即可视化结果
- utils: 工具模块，本文代码只涉及日志打印工具
- visual: 可视化模块
- main_tsp: TSP 模型主程序
- main_vrp: VRP 模型主程序
具体代码
参数与输入数据
TSP：
from datetime import datetime
import random
import math
from utils.logger import log_tsp as log
dts = datetime.now()
# nodes
NUM_NODE = 50
NUM_NODE_NAV = 20
LIST_NODE_UAV = list(range(NUM_NODE - NUM_NODE_NAV + 1, NUM_NODE + 1))
# coordinates
random.seed(2021)
RANGE_COORDINATE = (0, 100)
LIST_COORDINATE = [(random.randint(RANGE_COORDINATE[0], RANGE_COORDINATE[1]),
random.randint(RANGE_COORDINATE[0], RANGE_COORDINATE[1])) for _ in range(NUM_NODE)]
# distance
ORIGIN = (round((RANGE_COORDINATE[1] - RANGE_COORDINATE[0]) / 2),
round((RANGE_COORDINATE[1] - RANGE_COORDINATE[0]) / 2))
LIST_COORDINATE_ = [ORIGIN] + LIST_COORDINATE
MAT_DISTANCE = [[0.0 for _ in range(0, NUM_NODE + 1)] for _ in range(0, NUM_NODE + 1)]
range_wave = (0.8, 1.2)
for i in range(0, NUM_NODE + 1):
for j in range(0, NUM_NODE + 1):
distance = round(math.sqrt((LIST_COORDINATE_[i][0] - LIST_COORDINATE_[j][0]) ** 2
+ (LIST_COORDINATE_[i][1] - LIST_COORDINATE_[j][1]) ** 2)
* (range_wave[0] + random.random() * (range_wave[1] - range_wave[0])), 4)
MAT_DISTANCE[i][j] = distance
# cost
COST_UAV = 0.2
dte = datetime.now()
tm = round((dte - dts).seconds + (dte - dts).microseconds / (10 ** 6), 3)
log.info(msg="random data generating time: {} s".format(tm))
VRP：
from datetime import datetime
import random
import math
from utils.logger import log_vrp as log
dts = datetime.now()
# nodes
NUM_NODE = 50
NUM_NODE_NAV = 10
LIST_NODE_UAV = list(range(NUM_NODE - NUM_NODE_NAV + 1, NUM_NODE + 1))
# coordinates
random.seed(2021)
RANGE_COORDINATE = (0, 100)
LIST_COORDINATE = [(random.randint(RANGE_COORDINATE[0], RANGE_COORDINATE[1]),
random.randint(RANGE_COORDINATE[0], RANGE_COORDINATE[1])) for _ in range(NUM_NODE)]
# distance
ORIGIN = (round((RANGE_COORDINATE[1] - RANGE_COORDINATE[0]) / 2),
round((RANGE_COORDINATE[1] - RANGE_COORDINATE[0]) / 2))
LIST_COORDINATE_ = [ORIGIN] + LIST_COORDINATE
MAT_DISTANCE = [[0.0 for _ in range(0, NUM_NODE + 1)] for _ in range(0, NUM_NODE + 1)]
range_wave = (0.8, 1.2)
for i in range(0, NUM_NODE + 1):
for j in range(0, NUM_NODE + 1):
distance = round(math.sqrt((LIST_COORDINATE_[i][0] - LIST_COORDINATE_[j][0]) ** 2
+ (LIST_COORDINATE_[i][1] - LIST_COORDINATE_[j][1]) ** 2)
* (range_wave[0] + random.random() * (range_wave[1] - range_wave[0])), 4)
MAT_DISTANCE[i][j] = distance
# cost
COST_UAV = 0.1
# weight, load
upper_weight_item = 20
LIST_WEIGHT = [random.randint(0, upper_weight_item) for _ in range(NUM_NODE)]
UPPER_LOAD = 100
log.info(msg="total weight: {}".format(sum(LIST_WEIGHT)))
dte = datetime.now()
tm = round((dte - dts).seconds + (dte - dts).microseconds / (10 ** 6), 3)
log.info(msg="random data generating time: {} s".format(tm))
模型核心模块
在 TSP 模型中，通过 GG 模型的建模方式消除子回路；在 VRP 模型中，通过卡车载重约束的传递性消除子回路。
有关 TSP 模型的建模方式可见本人博客：https://blog.csdn.net/Zhang_0702_China/article/details/106983492
模型求解通过调用 Gurobi 求解器的方式实现，有关 Gurobi 求解器的 Python 调用，可见本人博客：https://blog.csdn.net/Zhang_0702_China/article/details/115520346
TSP：
from datetime import datetime
from typing import List, Dict, Tuple
from gurobipy import *
from utils.logger import log_tsp as log
def tsp_gg(num_node: int, list_node_uav: List[int], mat_distance: List[List[int]], cost_uav: float = 0.5) \
-> Tuple[List[int], Dict[int, Tuple[int, int]]]:
"""
TSP model, GG formulation
:param num_node: number of nodes
:param list_node_uav: nodes can be served by uav
:param mat_distance: distance matrix, 0 index for hub
:param cost_uav: cost coefficient of uav
:return: list_route: list of nodes in truck route
:return: dict_uav_route: dict of uav routes
"""
log.info(msg=">>> TSP model, GG formulation, start")
model = Model('tsp_gg')
""" variables """
# if truck flow from i to j
x = model.addVars([(i, j) for i in range(0, num_node + 1) for j in range(0, num_node + 1)], vtype=GRB.BINARY,
name='x_')
# if uav flow from i to j
y = model.addVars([(i, j) for i in range(0, num_node + 1) for j in range(0, num_node + 1)], vtype=GRB.BINARY,
name='y_')
# if served by truck
s = model.addVars([i for i in range(1, num_node + 1)], vtype=GRB.BINARY, name='s_')
# sub-loop elimination
a = model.addVars([(i, j) for i in range(0, num_node + 1) for j in range(0, num_node + 1)], vtype=GRB.CONTINUOUS,
name='a_')
""" constraints """
# cons 1: stream in / out
for i in range(0, num_node + 1):
# nodes can only served by truck
if i not in list_node_uav:
model.addConstr(quicksum(x[j, i] for j in range(0, num_node + 1)) == 1, name='cons_1_in_x_[{}]'.format(i))
model.addConstr(quicksum(x[i, j] for j in range(0, num_node + 1)) == 1, name='cons_1_out_x_[{}]'.format(i))
# nodes can served by truck or uav
else:
model.addConstr(quicksum(x[j, i] + y[j, i] for j in range(0, num_node + 1)) == 1,
name='cons_1_in_xy_[{}]'.format(i))
model.addConstr(quicksum(x[i, j] + y[i, j] for j in range(0, num_node + 1)) == 1,
name='cons_1_out_xy_[{}]'.format(i))
# truck or uav
model.addConstr(quicksum(y[j, i] for j in range(0, num_node + 1))
== quicksum(y[i, j] for j in range(0, num_node + 1)), name='cons_1_y[{}]'.format(i))
# cons 2: self-loop elimination
model.addConstr(quicksum(x[i, i] for i in range(0, num_node + 1)) == 0, name='cons_2_x')
model.addConstr(quicksum(y[i, i] for i in range(0, num_node + 1)) == 0, name='cons_2_y')
# cons 3: get, if served by truck
for i in range(1, num_node + 1):
model.addConstr(s[i] == quicksum(x[i, j] for j in range(0, num_node + 1)), name='cons_3_[{}]'.format(i))
# cons 4: sub-loop elimination
for i in range(1, num_node + 1):
list_n_i = list(range(0, i)) + list(range(i + 1, num_node + 1))
list_n_i_ori = list(range(1, i)) + list(range(i + 1, num_node + 1))
model.addConstr(quicksum(a[i, j] for j in list_n_i) - quicksum(a[j, i] for j in list_n_i_ori) == s[i],
name='cons_4_a_[{}]'.format(i))
for j in range(0, num_node + 1):
model.addConstr(a[i, j] <= num_node * x[i, j], name='cons_4_ax_[{},{}]'.format(i, j))
# cons 5: uav order
for j in list_node_uav:
for i in range(0, num_node + 1):
for k in range(0, num_node + 1):
model.addConstr(y[i, j] + y[j, k] <= 2 * x[i, k] + 1, name='cons_5_[{},{},{}]'.format(i, j, k))
# cons 6: only one uav
for i in range(0, num_node + 1):
model.addConstr(quicksum(y[i, j] for j in range(0, num_node + 1)) <= 1, name='cons_6_out_[{}]'.format(i))
model.addConstr(quicksum(y[j, i] for j in range(0, num_node + 1)) <= 1, name='cons_6_in_[{}]'.format(i))
""" objective & solve """
# obj: total weighted distance
cost = quicksum(x[i, j] * mat_distance[i][j] + y[i, j] * mat_distance[i][j] * cost_uav
for i in range(0, num_node + 1) for j in range(0, num_node + 1))
model.setObjective(cost, sense=GRB.MINIMIZE)
model.setParam(GRB.Param.TimeLimit, 300)
model.setParam(GRB.Param.MIPGap, 0.02)
dts_solve = datetime.now()
model.optimize()
dte_solve = datetime.now()
tm_solve = round((dte_solve - dts_solve).seconds + (dte_solve - dts_solve).microseconds / (10 ** 6), 3)
log.info(msg="solving time: {} s".format(tm_solve))
""" result """
x_ = model.getAttr('X', x)
y_ = model.getAttr('X', y)
s_ = model.getAttr('X', s)
# truck route
list_route = [0]
to = None
while to != 0:
for i in range(0, num_node + 1):
if x_[list_route[-1], i] > 0.9:
to = i
list_route.append(i)
break
# uav routes
list_node_uav_ = []
dict_uav_route = {}
for j in list_node_uav:
if s_[j] < 0.1:
list_node_uav_.append(j)
fr, to = None, None
for i in range(0, num_node + 1):
if y_[i, j] > 0.9:
fr = i
break
for k in range(0, num_node + 1):
if y_[j, k] > 0.9:
to = k
break
tup_fr_to = (fr, to)
dict_uav_route[j] = tup_fr_to
log.info(msg="nodes can be served by uav: {}".format(list_node_uav))
log.info(msg="nodes served by uav: {}".format(list_node_uav_))
log.info(msg="<<< TSP model, GG formulation, end")
return list_route, dict_uav_route
VRP：
from datetime import datetime
from typing import List, Dict, Tuple
from gurobipy import *
from utils.logger import log_vrp as log
def vrp_load(num_node: int, list_node_uav: List[int], list_weight: List[int], upper_load: int,
mat_distance: List[List[int]], cost_uav: float = 0.5) \
-> Tuple[List[List[int]], Dict[int, Tuple[int, int]]]:
"""
VRP model, load limit mode
:param num_node: number of nodes
:param list_node_uav: nodes can be served by uav
:param list_weight: weight of each node
:param upper_load: upper limit of vehicle loads
:param mat_distance: distance matrix, 0 index for hub
:param cost_uav: cost coefficient of uav
:return: list_routes: list of truck routes
:return: dict_uav_route: dict of uav routes
"""
log.info(msg=">>> VRP model, load limit mode, start")
model = Model('vrp_load')
""" variables """
# if truck flow from i to j
x = model.addVars([(i, j) for i in range(0, num_node + 1) for j in range(0, num_node + 1)], vtype=GRB.BINARY,
name='x_')
# if uav flow from i to j
y = model.addVars([(i, j) for i in range(0, num_node + 1) for j in range(0, num_node + 1)], vtype=GRB.BINARY,
name='y_')
# if served by truck
s = model.addVars([i for i in range(1, num_node + 1)], vtype=GRB.BINARY, name='s_')
# load limit: arc weight
z = model.addVars([(i, j) for i in range(0, num_node + 1) for j in range(0, num_node + 1)], ub=upper_load,
vtype=GRB.CONTINUOUS, name='a_')
""" constraints """
# cons 1: stream in / out, not including origin
for i in range(1, num_node + 1):
# nodes can only served by truck
if i not in list_node_uav:
model.addConstr(quicksum(x[j, i] for j in range(0, num_node + 1)) == 1, name='cons_1_in_x_[{}]'.format(i))
model.addConstr(quicksum(x[i, j] for j in range(0, num_node + 1)) == 1, name='cons_1_out_x_[{}]'.format(i))
# nodes can served by truck or uav
else:
model.addConstr(quicksum(x[j, i] + y[j, i] for j in range(0, num_node + 1)) == 1,
name='cons_1_in_xy_[{}]'.format(i))
model.addConstr(quicksum(x[i, j] + y[i, j] for j in range(0, num_node + 1)) == 1,
name='cons_1_out_xy_[{}]'.format(i))
# truck or uav
model.addConstr(quicksum(y[j, i] for j in range(0, num_node + 1))
== quicksum(y[i, j] for j in range(0, num_node + 1)), name='cons_1_y[{}]'.format(i))
# cons 2: self-loop elimination
model.addConstr(quicksum(x[i, i] for i in range(0, num_node + 1)) == 0, name='cons_2_x')
model.addConstr(quicksum(y[i, i] for i in range(0, num_node + 1)) == 0, name='cons_2_y')
# cons 3: get, if served by truck
for i in range(1, num_node + 1):
model.addConstr(s[i] == quicksum(x[i, j] for j in range(0, num_node + 1)), name='cons_3_[{}]'.format(i))
# cons 4: load limit, including sub-loop elimination
big_m = 10 ** 6
for j in range(1, num_node + 1):
for i in range(0, num_node + 1):
list_not_j = list(range(0, j)) + list(range(j + 1, num_node + 1))
list_uav_not_j = list_node_uav.copy()
if j in list_uav_not_j:
list_uav_not_j.remove(j)
model.addConstr(z[i, j] >= list_weight[j - 1] + quicksum(z[j, k] for k in list_not_j)
+ quicksum(y[j, u] * list_weight[u - 1] for u in list_uav_not_j) + (x[i, j] - 1) * big_m,
name='cons_4_[{},{}]'.format(i, j))
model.addConstr(z[i, j] <= x[i, j] * big_m, name='cons_4_zx_[{},{}]'.format(i, j))
# todo: sun-loop elimination: 2-node loop
if i:
model.addConstr(x[i, j] + x[j, i] <= 1, name='cons_4_loop_2[{},{}]'.format(i, j))
# cons 5: uav order
for j in list_node_uav:
for i in range(0, num_node + 1):
for k in range(0, num_node + 1):
model.addConstr(y[i, j] + y[j, k] <= 2 * x[i, k] + 1, name='cons_5_[{},{},{}]'.format(i, j, k))
# cons 6: only one uav
for i in range(0, num_node + 1):
model.addConstr(quicksum(y[i, j] for j in range(0, num_node + 1)) <= 1, name='cons_6_out_[{}]'.format(i))
model.addConstr(quicksum(y[j, i] for j in range(0, num_node + 1)) <= 1, name='cons_6_in_[{}]'.format(i))
# cons 7: valid inequality
model.addConstr(quicksum(x[0, j] for j in range(1, num_node + 1)) >= math.ceil(sum(list_weight) / upper_load),
name='cons_7')
""" objective & solve """
num_vehicle = quicksum(x[0, j] for j in range(1, num_node + 1))
sum_distance = quicksum(x[i, j] * mat_distance[i][j] + y[i, j] * mat_distance[i][j] * cost_uav
for i in range(0, num_node + 1) for j in range(0, num_node + 1))
model.setObjective(num_vehicle * big_m + sum_distance, sense=GRB.MINIMIZE)
model.setParam(GRB.Param.TimeLimit, 600)
model.setParam(GRB.Param.MIPGap, 0.05)
dts_solve = datetime.now()
model.optimize()
dte_solve = datetime.now()
tm_solve = round((dte_solve - dts_solve).seconds + (dte_solve - dts_solve).microseconds / (10 ** 6), 3)
log.info(msg="solving time: {} s".format(tm_solve))
""" result """
x_ = model.getAttr('X', x)
y_ = model.getAttr('X', y)
s_ = model.getAttr('X', s)
num_vehicle_ = int(sum(x_[0, j] for j in range(1, num_node + 1)))
log.info("total vehicles: {}".format(num_vehicle_))
# uav routes
list_node_uav_ = []
dict_uav_route = {}
for j in list_node_uav:
if s_[j] < 0.1:
list_node_uav_.append(j)
fr, to = None, None
for i in range(0, num_node + 1):
if y_[i, j] > 0.9:
fr = i
break
for k in range(0, num_node + 1):
if y_[j, k] > 0.9:
to = k
break
tup_fr_to = (fr, to)
dict_uav_route[j] = tup_fr_to
log.info(msg="nodes can be served by uav: {}".format(list_node_uav))
log.info(msg="nodes served by uav: {}".format(list_node_uav_))
# truck routes
list_routes = []
set_node = set(range(0, num_node + 1))
while len(set_node) > 1 + len(list_node_uav_): # todo: number of nodes served by truck
list_route_cur = [0]
to = None
while to != 0:
if to:
set_node.remove(to)
for i in set_node:
if x_[list_route_cur[-1], i] > 0.9:
to = i
list_route_cur.append(to)
break
list_routes.append(list_route_cur)
log.info(msg="<<< TSP model, GG formulation, end")
return list_routes, dict_uav_route
工具模块（日志打印工具）
源码中采用调用 logging 打印日志的方法。
参见本人另一篇博客：https://blog.csdn.net/Zhang_0702_China/article/details/107982958
import os
import logging
from logging.handlers import TimedRotatingFileHandler
PATH = os.path.dirname(os.path.dirname(__file__))
class Logger(object):
"""
log writer
"""
def __init__(self, log_name: str):
"""
log writer, initialise
:param log_name: file name of log
"""
self.log_name = log_name
self.log = logging.getLogger(name=self.log_name)
self.log.setLevel(logging.INFO)
# initialise logging
logging.basicConfig()
# output format
fmt_st = "%(asctime)s[%(levelname)s][%(processName)s][%(threadName)s]:%(message)s"
formatter = logging.Formatter(fmt=fmt_st)
# log file
path_root = os.path.join(PATH, "log") # root directory of log
if not os.path.exists(path_root):
os.makedirs(name=path_root)
path = os.path.join(path_root, self.log_name)
# level and format
file_handler = logging.handlers.TimedRotatingFileHandler(filename=path)
file_handler.setLevel(level=logging.INFO)
file_handler.setFormatter(fmt=formatter)
self.log.addHandler(hdlr=file_handler)
def info(self, msg: str):
"""
info
:param msg: info
:return: nothing
"""
msg_ = " " + msg
self.log.info(msg=msg_)
def error(self, msg: str):
"""
error info
:param msg: error info
:return: nothing
"""
msg_ = " " + msg
self.log.error(msg=msg_)
log_tsp = Logger(log_name='tsp.log')
log_vrp = Logger(log_name='vrp.log')
可视化模块
TSP：
import os
from typing import List, Dict, Tuple
import matplotlib.pyplot as plt
from config import tsp as config
PATH = os.path.dirname(os.path.dirname(__file__))
def scatter_route_tsp(list_route: List[int], dict_uav_route: Dict[int, Tuple[int, int]]):
"""
scatters and route of tsp result
:param list_route: list of nodes in truck route
:param dict_uav_route: dict of uav routes
:return: nothing
"""
num_node = config.NUM_NODE
list_node_uav = config.LIST_NODE_UAV
origin = config.ORIGIN
list_coordinate_ = config.LIST_COORDINATE_
range_coordinate = config.RANGE_COORDINATE
# scatters
plt.scatter(x=origin[0], y=origin[1], s=50, c='black', label='origin')
for i in range(1, num_node + 1):
color = 'blue' if i not in list_node_uav else 'red'
plt.scatter(x=list_coordinate_[i][0], y=list_coordinate_[i][1], s=20, c=color, label=str(i))
width = 0.2
head_width = 2
head_length = 3
alpha = 0.7
color_truck, color_uav = 'green', 'orange'
line_width = 0.5
# truck route
for i in range(len(list_route) - 1):
plt.arrow(x=list_coordinate_[list_route[i]][0], y=list_coordinate_[list_route[i]][1],
dx=list_coordinate_[list_route[i + 1]][0] - list_coordinate_[list_route[i]][0],
dy=list_coordinate_[list_route[i + 1]][1] - list_coordinate_[list_route[i]][1],
width=width, length_includes_head=True, head_width=head_width, head_length=head_length,
alpha=alpha, color=color_truck, linestyle='-', linewidth=line_width)
# uav route
for i in dict_uav_route.keys():
plt.arrow(x=list_coordinate_[dict_uav_route[i][0]][0], y=list_coordinate_[dict_uav_route[i][0]][1],
dx=list_coordinate_[i][0] - list_coordinate_[dict_uav_route[i][0]][0],
dy=list_coordinate_[i][1] - list_coordinate_[dict_uav_route[i][0]][1],
width=width, length_includes_head=True, head_width=head_width, head_length=head_length,
alpha=alpha, color=color_uav, linestyle='--', linewidth=line_width)
plt.arrow(x=list_coordinate_[i][0], y=list_coordinate_[i][1],
dx=list_coordinate_[dict_uav_route[i][1]][0] - list_coordinate_[i][0],
dy=list_coordinate_[dict_uav_route[i][1]][1] - list_coordinate_[i][1],
width=width, length_includes_head=True, head_width=head_width, head_length=head_length,
alpha=alpha, color=color_uav, linestyle='--', linewidth=line_width)
# x, y range
edge = 5
plt.xlim(range_coordinate[0] - edge, range_coordinate[1] + edge)
plt.ylim(range_coordinate[0] - edge, range_coordinate[1] + edge)
# save
path = os.path.join(PATH, "output/tsp.png")
plt.savefig(path)
VRP：
import os
from typing import List, Dict, Tuple
import matplotlib.pyplot as plt
from config import vrp as config
PATH = os.path.dirname(os.path.dirname(__file__))
def scatter_route_vrp(list_routes: List[List[int]], dict_uav_route: Dict[int, Tuple[int, int]]):
"""
scatters and route of vrp result
:param list_routes: list of truck route
:param dict_uav_route: dict of uav routes
:return: nothing
"""
num_node = config.NUM_NODE
list_node_uav = config.LIST_NODE_UAV
origin = config.ORIGIN
list_coordinate_ = config.LIST_COORDINATE_
range_coordinate = config.RANGE_COORDINATE
# scatters
plt.scatter(x=origin[0], y=origin[1], s=50, c='black', label='origin')
for i in range(1, num_node + 1):
color = 'blue' if i not in list_node_uav else 'red'
plt.scatter(x=list_coordinate_[i][0], y=list_coordinate_[i][1], s=20, c=color, label=str(i))
width = 0.2
head_width = 2
head_length = 3
alpha = 0.7
color_truck, color_uav = 'green', 'orange'
line_width = 0.5
# truck routes
for route in list_routes:
for i in range(len(route) - 1):
plt.arrow(x=list_coordinate_[route[i]][0], y=list_coordinate_[route[i]][1],
dx=list_coordinate_[route[i + 1]][0] - list_coordinate_[route[i]][0],
dy=list_coordinate_[route[i + 1]][1] - list_coordinate_[route[i]][1],
width=width, length_includes_head=True, head_width=head_width, head_length=head_length,
alpha=alpha, color=color_truck, linestyle='-', linewidth=line_width)
# uav routes
for i in dict_uav_route.keys():
plt.arrow(x=list_coordinate_[dict_uav_route[i][0]][0], y=list_coordinate_[dict_uav_route[i][0]][1],
dx=list_coordinate_[i][0] - list_coordinate_[dict_uav_route[i][0]][0],
dy=list_coordinate_[i][1] - list_coordinate_[dict_uav_route[i][0]][1],
width=width, length_includes_head=True, head_width=head_width, head_length=head_length,
alpha=alpha, color=color_uav, linestyle='--', linewidth=line_width)
plt.arrow(x=list_coordinate_[i][0], y=list_coordinate_[i][1],
dx=list_coordinate_[dict_uav_route[i][1]][0] - list_coordinate_[i][0],
dy=list_coordinate_[dict_uav_route[i][1]][1] - list_coordinate_[i][1],
width=width, length_includes_head=True, head_width=head_width, head_length=head_length,
alpha=alpha, color=color_uav, linestyle='--', linewidth=line_width)
# x, y range
edge = 5
plt.xlim(range_coordinate[0] - edge, range_coordinate[1] + edge)
plt.ylim(range_coordinate[0] - edge, range_coordinate[1] + edge)
# save
path = os.path.join(PATH, "output/vrp.png")
plt.savefig(path)
主程序
TSP（main_tsp.py）：
from datetime import datetime
from utils.logger import log_tsp as log
from config import tsp as config
from model.tsp import tsp_gg
from visual.tsp import scatter_route_tsp
DTS = datetime.now()
NUM_NODE = config.NUM_NODE
LIST_NODE_UAV = config.LIST_NODE_UAV.copy()
MAT_DISTANCE = config.MAT_DISTANCE.copy()
COST_UAV = config.COST_UAV
log.info(msg="number of nodes: {}".format(NUM_NODE))
log.info(msg="node can served by uav: {}".format(LIST_NODE_UAV))
# model
list_route, dict_uav_route = tsp_gg(num_node=NUM_NODE, list_node_uav=LIST_NODE_UAV, mat_distance=MAT_DISTANCE,
cost_uav=COST_UAV)
log.info(msg="truck route: {}".format(list_route))
for i in dict_uav_route.keys():
log.info(msg="uav served node: {}, {}".format(i, dict_uav_route[i]))
# visualisation
scatter_route_tsp(list_route=list_route, dict_uav_route=dict_uav_route)
DTE = datetime.now()
TM = round((DTE - DTS).seconds + (DTE - DTS).microseconds / (10 ** 6), 3)
log.info(msg="total time: {} s".format(TM))
VRP（main_vrp.py）：
from datetime import datetime
from utils.logger import log_vrp as log
from config import vrp as config
from model.vrp import vrp_load
from visual.vrp import scatter_route_vrp
DTS = datetime.now()
NUM_NODE = config.NUM_NODE
LIST_NODE_UAV = config.LIST_NODE_UAV.copy()
LIST_WEIGHT = config.LIST_WEIGHT
UPPER_LOAD = config.UPPER_LOAD
MAT_DISTANCE = config.MAT_DISTANCE.copy()
COST_UAV = config.COST_UAV
log.info(msg="number of nodes: {}".format(NUM_NODE))
log.info(msg="node can served by uav: {}".format(LIST_NODE_UAV))
# model
list_routes, dict_uav_route = vrp_load(
num_node=NUM_NODE, list_node_uav=LIST_NODE_UAV, list_weight=LIST_WEIGHT, upper_load=UPPER_LOAD,
mat_distance=MAT_DISTANCE, cost_uav=COST_UAV)
for i in range(len(list_routes)):
log.info(msg="truck route {}: {}".format(i + 1, list_routes[i]))
for i in dict_uav_route.keys():
log.info(msg="uav served node: {}, {}".format(i, dict_uav_route[i]))
# visualisation
scatter_route_vrp(list_routes=list_routes, dict_uav_route=dict_uav_route)
DTE = datetime.now()
TM = round((DTE - DTS).seconds + (DTE - DTS).microseconds / (10 ** 6), 3)
log.info(msg="total time: {} s".format(TM))
运行效果
TSP
如前面参数与输入数据模块所示，源码中的 TSP 算例有 50 个点，其中后面 20 个可使用无人机配送，无人机的距离成本系数设为 0.2（即同样的距离又无人机配送的成本为卡车配送的 20%），源码的运行日志如下：
2021-08-04 19:37:03,923[INFO][MainProcess][MainThread]: random data generating time: 0.004 s
2021-08-04 19:37:04,787[INFO][MainProcess][MainThread]: number of nodes: 50
2021-08-04 19:37:04,787[INFO][MainProcess][MainThread]: node can served by uav: [31, 32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 47, 48, 49, 50]
2021-08-04 19:37:04,787[INFO][MainProcess][MainThread]: >>> TSP model, GG formulation, start
2021-08-04 19:38:16,624[INFO][MainProcess][MainThread]: solving time: 49.773 s
2021-08-04 19:38:16,633[INFO][MainProcess][MainThread]: nodes can be served by uav: [31, 32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 47, 48, 49, 50]
2021-08-04 19:38:16,633[INFO][MainProcess][MainThread]: nodes served by uav: [31, 32, 33, 36, 37, 39, 40, 41, 42, 44, 49, 50]
2021-08-04 19:38:16,634[INFO][MainProcess][MainThread]: <<< TSP model, GG formulation, end
2021-08-04 19:38:16,690[INFO][MainProcess][MainThread]: truck route: [0, 34, 24, 27, 5, 1, 21, 14, 35, 48, 12, 43, 17, 20, 18, 19, 2, 26, 15, 8, 47, 13, 29, 38, 28, 9, 22, 6, 4, 30, 10, 11, 25, 46, 16, 3, 23, 45, 7, 0]
2021-08-04 19:38:16,691[INFO][MainProcess][MainThread]: uav served node: 31, (20, 18)
2021-08-04 19:38:16,691[INFO][MainProcess][MainThread]: uav served node: 32, (10, 11)
2021-08-04 19:38:16,691[INFO][MainProcess][MainThread]: uav served node: 33, (22, 6)
2021-08-04 19:38:16,691[INFO][MainProcess][MainThread]: uav served node: 36, (1, 21)
2021-08-04 19:38:16,691[INFO][MainProcess][MainThread]: uav served node: 37, (13, 29)
2021-08-04 19:38:16,691[INFO][MainProcess][MainThread]: uav served node: 39, (9, 22)
2021-08-04 19:38:16,691[INFO][MainProcess][MainThread]: uav served node: 40, (17, 20)
2021-08-04 19:38:16,691[INFO][MainProcess][MainThread]: uav served node: 41, (18, 19)
2021-08-04 19:38:16,691[INFO][MainProcess][MainThread]: uav served node: 42, (26, 15)
2021-08-04 19:38:16,691[INFO][MainProcess][MainThread]: uav served node: 44, (21, 14)
2021-08-04 19:38:16,691[INFO][MainProcess][MainThread]: uav served node: 49, (19, 2)
2021-08-04 19:38:16,691[INFO][MainProcess][MainThread]: uav served node: 50, (6, 4)
2021-08-04 19:38:17,174[INFO][MainProcess][MainThread]: total time: 72.387 s
可视化结果图：
VRP
关于 VRP 模型的算例，源码中的设置为 50 个点，其中最后 10 个点可使用无人机配送，无人机的距离成本系数设为 0.1，每辆车的载重上限为 100，每个物品的重量上限为 20，源码的运行日志如下：
2021-08-04 19:40:21,300[INFO][MainProcess][MainThread]: total weight: 486
2021-08-04 19:40:21,300[INFO][MainProcess][MainThread]: random data generating time: 0.004 s
2021-08-04 19:40:22,168[INFO][MainProcess][MainThread]: number of nodes: 50
2021-08-04 19:40:22,168[INFO][MainProcess][MainThread]: node can served by uav: [41, 42, 43, 44, 45, 46, 47, 48, 49, 50]
2021-08-04 19:40:22,168[INFO][MainProcess][MainThread]: >>> VRP model, load limit mode, start
2021-08-04 19:41:23,075[INFO][MainProcess][MainThread]: solving time: 38.906 s
2021-08-04 19:41:23,092[INFO][MainProcess][MainThread]: total vehicles: 5
2021-08-04 19:41:23,093[INFO][MainProcess][MainThread]: nodes can be served by uav: [41, 42, 43, 44, 45, 46, 47, 48, 49, 50]
2021-08-04 19:41:23,094[INFO][MainProcess][MainThread]: nodes served by uav: [42, 43, 44, 45, 46, 47, 48, 49, 50]
2021-08-04 19:41:23,094[INFO][MainProcess][MainThread]: <<< TSP model, GG formulation, end
2021-08-04 19:41:23,175[INFO][MainProcess][MainThread]: truck route 1: [0, 6, 4, 30, 25, 11, 10, 32, 3, 16, 23, 0]
2021-08-04 19:41:23,175[INFO][MainProcess][MainThread]: truck route 2: [0, 7, 33, 22, 39, 9, 13, 29, 37, 38, 28, 0]
2021-08-04 19:41:23,175[INFO][MainProcess][MainThread]: truck route 3: [0, 19, 2, 26, 15, 8, 0]
2021-08-04 19:41:23,175[INFO][MainProcess][MainThread]: truck route 4: [0, 34, 24, 36, 1, 5, 27, 0]
2021-08-04 19:41:23,175[INFO][MainProcess][MainThread]: truck route 5: [0, 41, 31, 18, 20, 17, 40, 12, 35, 14, 21, 0]
2021-08-04 19:41:23,176[INFO][MainProcess][MainThread]: uav served node: 42, (26, 15)
2021-08-04 19:41:23,176[INFO][MainProcess][MainThread]: uav served node: 43, (19, 2)
2021-08-04 19:41:23,176[INFO][MainProcess][MainThread]: uav served node: 44, (36, 1)
2021-08-04 19:41:23,176[INFO][MainProcess][MainThread]: uav served node: 45, (34, 24)
2021-08-04 19:41:23,176[INFO][MainProcess][MainThread]: uav served node: 46, (3, 16)
2021-08-04 19:41:23,176[INFO][MainProcess][MainThread]: uav served node: 47, (15, 8)
2021-08-04 19:41:23,176[INFO][MainProcess][MainThread]: uav served node: 48, (35, 14)
2021-08-04 19:41:23,176[INFO][MainProcess][MainThread]: uav served node: 49, (2, 26)
2021-08-04 19:41:23,176[INFO][MainProcess][MainThread]: uav served node: 50, (0, 6)
2021-08-04 19:41:23,652[INFO][MainProcess][MainThread]: total time: 61.484 s
可视化结果图：