VRP问题

哈朗
2023-12-01

最近一个物流配送车辆调度系统的项目要求带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

找到数据集改名

 类似资料: