VRP问题

最近一个物流配送车辆调度系统的项目要求带VRP的功能，以下是一些开源框架、API，和重点尝试的禁忌搜索。

 

用c-w节约启发式算法解决的单车型送货非满载vsp问题

https://www.write-bug.com/article/173.html

API：

http://demo.smartvrp.com/eu

https://georepublic.info/en/products/smartvrp/

 

带时间窗的车辆路径问题(Vehicle Routing Problem with Time

 Windows, VRPTW)是对物流配送管理的核心问题——配送车辆调度

 的问题抽象,其是在基本VRP基础上添加了时间窗约束衍生而来的,

 可以将VRPTW描述为:使车辆从站点出发服务用户,完成用户需求

 后仍返回站点,规定每个用户只能被一辆车服务且仅服务一次,且对

 用户的服务必须在用户事先指定的时间窗内进行,问题的优化目标是

 如何选择适当的路径,使得在满足以上约束条件的情况下,完成全部

 需求花费的总成本最小或总利润最大。

 

Java框架Jsprit: https://github.com/graphhopper/jsprit

 

遗传算法https://github.com/iRB-Lab/py-ga-VRPTW

https://github.com/wasinski/VRP

vrp模拟退火算法解释：https://github.com/lzane/VRP-using-SA-with-Matlab

java web应用：https://github.com/kiegroup/optaweb-vehicle-routing

禁忌搜索java控制台打印）https://github.com/nimich/VehicleRouting

蚁群py：https://github.com/AuxinJeron/ACS-VRP

 

配送系统：http://blog.sina.com.cn/s/blog_15e199e600102yb6g.html

 

Matlab：[ts]  里面介绍的是使用禁忌搜索求解vrp，只要修改下数据就可以使用，用的是MATLAB写的
[slotted-waveguide-antenna-parameters]  slotted waveguide, length, width, offset
[PSOlssvm]  粒子群优化参数的LSSVM，并对啤酒数据进行分类
[TS_VRP]  用遗传算法根据各个客户点的距离，需求，容量限制寻找最优路径从而使成本最低
[FA_constrained_optimization]  Firefly Algorithm for constrained optimization using % % for the design of a spring

 

生鲜o2o配送开源系统,包括Android源码+SSH后台管理系统：

https://download.csdn.net/download/df199111/11133203

试用菜鸟车辆路径优化算法API：菜鸟车辆路径规划算法

利用百度地图实现送货路线智能规划，使用节约里程法，纯js实现：

https://gitee.com/tankebign/routeplanning/

高德车辆路线规划API：https://lbs.amap.com/api/android-sdk/guide/route-plan/truck

地址识别js：https://github.com/akebe/address-parse

Php地址解析：https://github.com/pupuk/address-smart-parse

遗传算法

https://github.com/iRB-Lab/py-ga-VRPTW

具有时间窗口的基于遗传算法的车辆路由问题的 Python 实现

禁忌搜索TC代码

8     17   E:\studyMaterial\学习\城市交通\物流配送课设\Tabu Search.cpp [Error] bios.h: No such file or directory

是个TurboC代码

34   9     E:\studyMaterial\学习\城市交通\物流配送课设\Tabu Search.cpp [Error] 'clrscr' was not declared in this scope

 

改成：system("CLS");

/*ddd 解的评价值（即各车辆行驶的总里程）,q 当前车辆目前的载重量,d 当前车辆目前行驶距离,s 当前车辆的行驶时间*/

 

TabuSearch

https://github.com/wasinski/VRP

Least Cost Search最小成本检索

 

Importing TSPLIB euc2d format

 

Runtests（无bash，用python命令运行）

python3 -m tests.tests_import 1>test.log python3 -m tests.tests_datamapper 1>>test.log python3 -m tests.tests_baseobjects 1>>test.log python3 -m tests.tests_greedy 1>>test.log贪婪 python3 -m tests.tests_branchnbound 1>>test.log分支界定 python3 -m tests.tests_tabu 1>>test.log禁忌

运行测试集

(base) C:\Users\laugo>activate tensorflow   (tensorflow) C:\Users\laugo>cd /d D:\anacondaProject\VRP-master   (tensorflow) D:\anacondaProject\VRP-master>python -m tests.tests_import 1>test.log ..... ---------------------------------------------------------------------- Ran 5 tests in 0.018s   OK (tensorflow) D:\anacondaProject\VRP-master>python -m tests.tests_datamapper 1>>test.log . ---------------------------------------------------------------------- Ran 1 test in 0.002s   OK (tensorflow) D:\anacondaProject\VRP-master>python -m tests.tests_baseobjects 1>>test.log .......... ---------------------------------------------------------------------- Ran 10 tests in 0.002s   OK

使用数据集eil23.vrp并改文件名与name属性为E-n23-k3

(tensorflow) D:\anacondaProject\VRP-master>python -m tests.tests_greedy 1>>test.log ...... ---------------------------------------------------------------------- Ran 6 tests in 0.022s   OK

test.log中打印出

vals: 1462.5938995996864 794.1682489781883

 

数据集：http://www.omegaxyz.com/2018/12/03/tsplib-matlab/

DIMENSION : 6 EDGE_WEIGHT_TYPE : EUC_2D指定如何给出边权重(或距离)。 CAPACITY : 2500指定 CVRP 中的卡车容量 NODE_COORD_SECTION节点坐标 1 145 215 2 151 264 3 159 261 4 130 254 5 128 252 6 163 247 DEMAND_SECTION结点需求 1 0 2 1100 3 700 4 800 5 1400 6 2100 DEPOT_SECTION备用站点节点  1  -1 EOF

 

python的argparse模块add_argument详解：

https://blog.csdn.net/u013177568/article/details/62432761/

指定action='store_true'或者‘store_False’之后，在运行程序添加参数时直接输入变量名，可以省略对应的默认值True或者False

 

parser.add_argument('--inner-batch', help='inner batch size', choices=[1,5,10], default=5, type=int)

就比如上面的 '--inner-batch'  ，例如在启动程序demo.py时，在终端中输入 ./demo.py --inner-batch 10  就会将inner-batch这个选项的参数设置为10，不给参数时使用default参数5。

加参数后报错

(tensorflow) D:\anacondaProject\VRP-master>python CVRPSolver.py -ProblemInstance test.log -Tabu Traceback (most recent call last):   File "CVRPSolver.py", line 3, in <module>     main()   File "D:\anacondaProject\VRP-master\code\solver.py", line 29, in main     raw_data.import_data(problem_path)   File "D:\anacondaProject\VRP-master\code\datamapping.py", line 22, in import_data     self._create_distance_matrix(self.node_coordinates_list, int(self.info["DIMENSION"])) KeyError: 'DIMENSION' 使用文件里没有Name属性

python CVRPSolver.py -ProblemInstance ./tests/cvrp4.test -Tabu

(tensorflow) D:\anacondaProject\VRP-master>python CVRPSolver.py -ProblemInstance ./tests/E-n23-k3.vrp -Tabu Starting tabu search No more swaps found - ending iterations! time: 1.203125 initial value from greedy heuristic was: 794.1682489781883         value after running tabu search: 693.9407907610362 routes: vehicle 1: 1, 14, 11, 1, vehicle 2: 1, 10, 9, 5, 6, 22, 15, 18, 23, 21, 20, 19, 1, vehicle 3: 1, 13, 7, 2, 3, 4, 17, 16, 12, 8, 1,

查看源代码：

adjacency_matrix_list = \             self._create_distance_matrix(self.node_coordinates_list, int(self.info["DIMENSION"]))

def _create_distance_matrix(self, my_node_coordinates_list, my_dimension):         ncl = deque(my_node_coordinates_list[:])         matrix = []         while ncl:             row = [0] * (my_dimension + 1 - len(ncl))             node1 = ncl.popleft()             for node2 in ncl:                 row.append(euclidian_distance(node1, node2))             matrix.append(row)           for i in range(my_dimension):  # mirroring the matrix             for j in range(my_dimension):                 try:                     matrix[j][i] = matrix[i][j]                 except IndexError as e:                     print("##ERROR!##\nBad indexing: " + str((i, j)))                     print("that definitly shouldnt happen, it >might< be a problem with the imported file")                     raise e           return matrix

raw_data.import_data(problem_path)

def import_data(self, filename):         self._read_file(filename)         self.info, break_lines = self._read_info()         self.node_coordinates_list, demand_list = \             self._return_nodes_and_delivery_lists(break_lines)         adjacency_matrix_list = \             self._create_distance_matrix(self.node_coordinates_list, int(self.info["DIMENSION"]))

需要打开参数传入的文件：ProblemInstance

测试集报错

ERROR: test_get_nearest_node (__main__.TestGreedy) ---------------------------------------------------------------------- Traceback (most recent call last):   File "D:\anacondaProject\VRP-master\tests\tests_greedy.py", line 13, in setUp     raw_data.import_data("./tests/E-n23-k3.vrp")   File "D:\anacondaProject\VRP-master\code\datamapping.py", line 17, in import_data     self._read_file(filename)   File "D:\anacondaProject\VRP-master\code\datamapping.py", line 29, in _read_file     with open(my_filename, "rt") as f: FileNotFoundError: [Errno 2] No such file or directory: './tests/E-n23-k3.vrp'

创建.vrp文件后再运行报错

FAIL: test_greedy_sort_false (__main__.TestGreedy) ---------------------------------------------------------------------- Traceback (most recent call last):   File "D:\anacondaProject\VRP-master\tests\tests_greedy.py", line 51, in test_greedy_sort_false     self.assertEqual(count, 28)  # 28 because every vehicle stats and ends at the depot AssertionError: 13 != 28   ====================================================================== FAIL: test_greedy_sort_true (__main__.TestGreedy) ---------------------------------------------------------------------- Traceback (most recent call last):   File "D:\anacondaProject\VRP-master\tests\tests_greedy.py", line 64, in test_greedy_sort_true     self.assertEqual(count, 28)  # 28 because every vehicle stats and ends at the depot AssertionError: 13 != 28

找到数据集改名