本文为本人博客《一种无人机配合卡车配送的车辆路径规划模型》的代码分享。
由于近期此文的关注者较多，代码分享较为不便，因此决定专门写一篇博客以提供源码。
感谢各位博友关注，本人能力有限，如有错误，还请及时批评指正！
原文链接：https://blog.csdn.net/Zhang_0702_China/article/details/115215219

代码文件结构

代码的文件结构如下：

config: 参数、输入数据（随机生成）
docs: 模型文档、参考文献（见前面原文链接）
log: 运行日志
model: 模型核心模块
output: 输出文件，即可视化结果
utils: 工具模块，本文代码只涉及日志打印工具
visual: 可视化模块
main_tsp.py: TSP 模型主程序
main_vrp.py: VRP 模型主程序

把后面提供的代码粘贴到对应文件即可运行。
文件结构

具体代码

参数与输入数据

TSP：

from datetime import datetime
import random
import mathfrom utils.logger import log_tsp as logdts = 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.2dte = 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 mathfrom utils.logger import log_vrp as logdts = 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, Tuplefrom gurobipy import *from utils.logger import log_tsp as logdef 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 jx = 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 jy = 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 trucks = model.addVars([i for i in range(1, num_node + 1)], vtype=GRB.BINARY, name='s_')# sub-loop eliminationa = 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 / outfor i in range(0, num_node + 1):# nodes can only served by truckif 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 uavelse: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 uavmodel.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 eliminationmodel.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 truckfor 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 eliminationfor 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 orderfor 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 uavfor 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 distancecost = quicksum(x[i, j] * mat_distance[i][j] + y[i, j] * mat_distance[i][j] * cost_uavfor 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 routelist_route = [0]to = Nonewhile to != 0:for i in range(0, num_node + 1):if x_[list_route[-1], i] > 0.9:to = ilist_route.append(i)break# uav routeslist_node_uav_ = []dict_uav_route = {}for j in list_node_uav:if s_[j] < 0.1:list_node_uav_.append(j)fr, to = None, Nonefor i in range(0, num_node + 1):if y_[i, j] > 0.9:fr = ibreakfor k in range(0, num_node + 1):if y_[j, k] > 0.9:to = kbreaktup_fr_to = (fr, to)dict_uav_route[j] = tup_fr_tolog.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, Tuplefrom gurobipy import *from utils.logger import log_vrp as logdef 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 jx = 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 jy = 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 trucks = model.addVars([i for i in range(1, num_node + 1)], vtype=GRB.BINARY, name='s_')# load limit: arc weightz = 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 originfor i in range(1, num_node + 1):# nodes can only served by truckif 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 uavelse: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 uavmodel.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 eliminationmodel.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 truckfor 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 eliminationbig_m = 10 ** 6for 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 loopif i:model.addConstr(x[i, j] + x[j, i] <= 1, name='cons_4_loop_2[{},{}]'.format(i, j))# cons 5: uav orderfor 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 uavfor 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 inequalitymodel.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_uavfor 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 routeslist_node_uav_ = []dict_uav_route = {}for j in list_node_uav:if s_[j] < 0.1:list_node_uav_.append(j)fr, to = None, Nonefor i in range(0, num_node + 1):if y_[i, j] > 0.9:fr = ibreakfor k in range(0, num_node + 1):if y_[j, k] > 0.9:to = kbreaktup_fr_to = (fr, to)dict_uav_route[j] = tup_fr_tolog.info(msg="nodes can be served by uav:  {}".format(list_node_uav))log.info(msg="nodes served by uav:  {}".format(list_node_uav_))# truck routeslist_routes = []set_node = set(range(0, num_node + 1))while len(set_node) > 1 + len(list_node_uav_):  # todo: number of nodes served by trucklist_route_cur = [0]to = Nonewhile to != 0:if to:set_node.remove(to)for i in set_node:if x_[list_route_cur[-1], i] > 0.9:to = ilist_route_cur.append(to)breaklist_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 TimedRotatingFileHandlerPATH = 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_nameself.log = logging.getLogger(name=self.log_name)self.log.setLevel(logging.INFO)# initialise logginglogging.basicConfig()# output formatfmt_st = "%(asctime)s[%(levelname)s][%(processName)s][%(threadName)s]:%(message)s"formatter = logging.Formatter(fmt=fmt_st)# log filepath_root = os.path.join(PATH, "log")  # root directory of logif not os.path.exists(path_root):os.makedirs(name=path_root)path = os.path.join(path_root, self.log_name)# level and formatfile_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_ = " " + msgself.log.info(msg=msg_)def error(self, msg: str):"""error info:param msg:  error info:return: nothing"""msg_ = " " + msgself.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 pltfrom config import tsp as configPATH = 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_NODElist_node_uav = config.LIST_NODE_UAVorigin = config.ORIGINlist_coordinate_ = config.LIST_COORDINATE_range_coordinate = config.RANGE_COORDINATE# scattersplt.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.2head_width = 2head_length = 3alpha = 0.7color_truck, color_uav = 'green', 'orange'line_width = 0.5# truck routefor 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 routefor 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 rangeedge = 5plt.xlim(range_coordinate[0] - edge, range_coordinate[1] + edge)plt.ylim(range_coordinate[0] - edge, range_coordinate[1] + edge)# savepath = os.path.join(PATH, "output/tsp.png")plt.savefig(path)

VRP：

import os
from typing import List, Dict, Tuple
import matplotlib.pyplot as pltfrom config import vrp as configPATH = 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_NODElist_node_uav = config.LIST_NODE_UAVorigin = config.ORIGINlist_coordinate_ = config.LIST_COORDINATE_range_coordinate = config.RANGE_COORDINATE# scattersplt.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.2head_width = 2head_length = 3alpha = 0.7color_truck, color_uav = 'green', 'orange'line_width = 0.5# truck routesfor 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 routesfor 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 rangeedge = 5plt.xlim(range_coordinate[0] - edge, range_coordinate[1] + edge)plt.ylim(range_coordinate[0] - edge, range_coordinate[1] + edge)# savepath = os.path.join(PATH, "output/vrp.png")plt.savefig(path)

主程序

TSP（main_tsp.py）：

from datetime import datetimefrom 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_tspDTS = 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 datetimefrom 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_vrpDTS = 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

可视化结果图：
TSP 可视化结果

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

可视化结果图：
VRP 可视化结果