云筹优化APS集成多种优化调度算法，不仅仅可以解决车间调度问题，而且可以解决VRPTW带时间窗的车辆路径配送优化调度问题，这篇文章描述 云筹优化APS基于禁忌搜索算法求解VRPTW问题。
VRPTW问题可描述为：假设一个配送中心为周围若干个位于不同地理位置、且对货物送达时间有不相同要求的客户点提供配送服务。其中，配送中心全部用于运行的车辆都是同一型号的（即拥有相同的容量）；配送中心对车辆出入的时间有限制；车辆在所有客户点有相同的停留服务时间。
给出的连通G=(N,A)中，n+1个位置节点表示为集合N={0,1,2,...,n}，连接节点之间的边表示为集合A={(i,j):i≠j∈N}。其中节点0是仓库，剩余每个节点对应一个客户。假设车辆的速度恒定（即从节点i到节点j的行驶时间tij在数值上与其欧式距离dij相等）。可用的车辆数表示为m，所有车必须从位置0开始并回到位置0。每个点节i属于N且带有时间窗[a_i, b_i]，其中a_i和b_i分别表示节点i最早和最晚允许开始接受货物的时间。若节点i被选中且在路线r中，则决策变量y_{ri}的值为1，否则为0。若边(i,j)被选中且在路线r中，则决策变量x_{rij}的值为1，否则为0。路线r中车辆抵达客户i的时间点用决策变量s_{ri}表示。在车辆早抵达的情况下，车辆必须等候至时间窗起始时间点。若抵达时间点没有超出时间窗的结束时间点，则服务成功（即获得利润）。
采取读取文本格式来作为数据输入的形式，具体格式见下表：
|
序号 |
横坐标 |
纵坐标 |
服务量 |
时间窗起始 |
时间窗结束 |
服务时间 |
|
1 |
35.00 |
35.00 |
0.00 |
0.00 |
230．00 |
0.00 |
|
2 |
41.00 |
49.00 |
10.00 |
161.00 |
171.00 |
10.00 |
由上表可知，输入数据为一行七列的形式，依次为对应点的序号、横坐标、纵坐标、所需服务量、服务时间窗起始时间点、服务时间窗结束时间点和服务所需时间。由此可见，节点1为仓库（depot）,其他节点为待服务点。完整数据格式见文章 末尾附录
第一步：APS数据建模，将 VRPTW问题中的每一个配送任务作为一个订单导入APS系统，并将所需服务量、服务时间窗起始时间点、服务时间窗结束时间点和服务所需时间，转换为时分秒的时间，
其中服务时间窗起始时间点对应订单下单时间（即最早开始时间），服务时间窗结束时间点对应订单交货期（即最晚结束时间），服务时间对应生产制造时间数据如下图所示，：
第二步：APS资源建模，由于不限制车辆数量，假设车辆数量与任务数量相同，如下图所示，系统导入100台车辆，算法需要自动计算需要派几台车辆配送任务最合适。
第三步：配置APS排程策略，使用禁忌搜索算法求解，计算每个任务的前处理时间（从前一个任务地点（配送中心）到当前任务位置的距离），生产时间(服务时间+提前到达当前任务位置的等待时间)，后处理时间（最后一个任务完成后返回配送中心的距离）。
计划开始时间（出发去下一个位置的开始时间），计划结束时间（任务完成时间），计划主资源（任务选择那一台车辆进行配送）
第四步：APS资源甘特图上，可视化展示优化调度结果，资源甘特图上：一行表示一台配送车辆的任务安排，不同颜色的图块表示任务处理的时间与转移时间。可以看出每台配送车辆在0点出发，23点返回配送中心
第五步：APS提供数据看板，直观展示每台车辆的任务安排，管理人员可以直接按照计划结果进行车辆调度
云筹优化APS 支持多种算法解决VRPTW问题，本文采用禁忌搜索算法，基本步骤如下：
① 初始化
利用贪婪算法等局部搜索算法生成一个初始解，清空禁忌表，设置禁忌长度。
② 邻域搜索产生候选解
根据步骤①产生初始解，通过搜索算子（search operators），如relocation、exchange、2-opt等，产生候选解(candidate solution)，并计算各个候选解的适应值（即解对应的目标函数值）。
③ 选择最好的候选解
从步骤②产生的所有候选解中选出适应值最好的候选解，将其与当前最好解(即搜索算法开始到现在找到的最好解)进行比较，如果优于当前最好解，那么就不考虑其是否被禁忌，用这个最好的候选解来更新当前最好解，并且作为下一个迭代的当前解，然后将对应的操作加入禁忌表；如果不优于当前最好解，就从所有候选解中选出不在禁忌状态下的最好解作为新的当前解，然后将对应操作加入禁忌表。
④ 判断终止条件
若满足终止条件，则立即停止并输出当前最好解；否则继续搜索。一般终止条件为是否到达一定的迭代次数或者达到了一个时间限制。
禁忌搜索算法流程图：
禁忌搜索算法涉及编码解码（Encoding and decoding）、搜索算子（search operators）、邻域 （Neighborhood）、禁忌表（Tabu list）、禁忌长度（Tabu tenure）、候选解（Candidate solution）、藐视准则（Aspiration criterion）等关键组成部分。
附录：R101数据
1 35.00 35.00 0.00 0.00 230.00 0.00
2 41.00 49.00 10.00 161.00 171.00 10.00
3 35.00 17.00 7.00 50.00 60.00 10.00
4 55.00 45.00 13.00 116.00 126.00 10.00
5 55.00 20.00 19.00 149.00 159.00 10.00
6 15.00 30.00 26.00 34.00 44.00 10.00
7 25.00 30.00 3.00 99.00 109.00 10.00
8 20.00 50.00 5.00 81.00 91.00 10.00
9 10.00 43.00 9.00 95.00 105.00 10.00
10 55.00 60.00 16.00 97.00 107.00 10.00
11 30.00 60.00 16.00 124.00 134.00 10.00
12 20.00 65.00 12.00 67.00 77.00 10.00
13 50.00 35.00 19.00 63.00 73.00 10.00
14 30.00 25.00 23.00 159.00 169.00 10.00
15 15.00 10.00 20.00 32.00 42.00 10.00
16 30.00 5.00 8.00 61.00 71.00 10.00
17 10.00 20.00 19.00 75.00 85.00 10.00
18 5.00 30.00 2.00 157.00 167.00 10.00
19 20.00 40.00 12.00 87.00 97.00 10.00
20 15.00 60.00 17.00 76.00 86.00 10.00
21 45.00 65.00 9.00 126.00 136.00 10.00
22 45.00 20.00 11.00 62.00 72.00 10.00
23 45.00 10.00 18.00 97.00 107.00 10.00
24 55.00 5.00 29.00 68.00 78.00 10.00
25 65.00 35.00 3.00 153.00 163.00 10.00
26 65.00 20.00 6.00 172.00 182.00 10.00
27 45.00 30.00 17.00 132.00 142.00 10.00
28 35.00 40.00 16.00 37.00 47.00 10.00
29 41.00 37.00 16.00 39.00 49.00 10.00
30 64.00 42.00 9.00 63.00 73.00 10.00
31 40.00 60.00 21.00 71.00 81.00 10.00
32 31.00 52.00 27.00 50.00 60.00 10.00
33 35.00 69.00 23.00 141.00 151.00 10.00
34 53.00 52.00 11.00 37.00 47.00 10.00
35 65.00 55.00 14.00 117.00 127.00 10.00
36 63.00 65.00 8.00 143.00 153.00 10.00
37 2.00 60.00 5.00 41.00 51.00 10.00
38 20.00 20.00 8.00 134.00 144.00 10.00
39 5.00 5.00 16.00 83.00 93.00 10.00
40 60.00 12.00 31.00 44.00 54.00 10.00
41 40.00 25.00 9.00 85.00 95.00 10.00
42 42.00 7.00 5.00 97.00 107.00 10.00
43 24.00 12.00 5.00 31.00 41.00 10.00
44 23.00 3.00 7.00 132.00 142.00 10.00
45 11.00 14.00 18.00 69.00 79.00 10.00
46 6.00 38.00 16.00 32.00 42.00 10.00
47 2.00 48.00 1.00 117.00 127.00 10.00
48 8.00 56.00 27.00 51.00 61.00 10.00
49 13.00 52.00 36.00 165.00 175.00 10.00
50 6.00 68.00 30.00 108.00 118.00 10.00
51 47.00 47.00 13.00 124.00 134.00 10.00
52 49.00 58.00 10.00 88.00 98.00 10.00
53 27.00 43.00 9.00 52.00 62.00 10.00
54 37.00 31.00 14.00 95.00 105.00 10.00
55 57.00 29.00 18.00 140.00 150.00 10.00
56 63.00 23.00 2.00 136.00 146.00 10.00
57 53.00 12.00 6.00 130.00 140.00 10.00
58 32.00 12.00 7.00 101.00 111.00 10.00
59 36.00 26.00 18.00 200.00 210.00 10.00
60 21.00 24.00 28.00 18.00 28.00 10.00
61 17.00 34.00 3.00 162.00 172.00 10.00
62 12.00 24.00 13.00 76.00 86.00 10.00
63 24.00 58.00 19.00 58.00 68.00 10.00
64 27.00 69.00 10.00 34.00 44.00 10.00
65 15.00 77.00 9.00 73.00 83.00 10.00
66 62.00 77.00 20.00 51.00 61.00 10.00
67 49.00 73.00 25.00 127.00 137.00 10.00
68 67.00 5.00 25.00 83.00 93.00 10.00
69 56.00 39.00 36.00 142.00 152.00 10.00
70 37.00 47.00 6.00 50.00 60.00 10.00
71 37.00 56.00 5.00 182.00 192.00 10.00
72 57.00 68.00 15.00 77.00 87.00 10.00
73 47.00 16.00 25.00 35.00 45.00 10.00
74 44.00 17.00 9.00 78.00 88.00 10.00
75 46.00 13.00 8.00 149.00 159.00 10.00
76 49.00 11.00 18.00 69.00 79.00 10.00
77 49.00 42.00 13.00 73.00 83.00 10.00
78 53.00 43.00 14.00 179.00 189.00 10.00
79 61.00 52.00 3.00 96.00 106.00 10.00
80 57.00 48.00 23.00 92.00 102.00 10.00
81 56.00 37.00 6.00 182.00 192.00 10.00
82 55.00 54.00 26.00 94.00 104.00 10.00
83 15.00 47.00 16.00 55.00 65.00 10.00
84 14.00 37.00 11.00 44.00 54.00 10.00
85 11.00 31.00 7.00 101.00 111.00 10.00
86 16.00 22.00 41.00 91.00 101.00 10.00
87 4.00 18.00 35.00 94.00 104.00 10.00
88 28.00 18.00 26.00 93.00 103.00 10.00
89 26.00 52.00 9.00 74.00 84.00 10.00
90 26.00 35.00 15.00 176.00 186.00 10.00
91 31.00 67.00 3.00 95.00 105.00 10.00
92 15.00 19.00 1.00 160.00 170.00 10.00
93 22.00 22.00 2.00 18.00 28.00 10.00
94 18.00 24.00 22.00 188.00 198.00 10.00
95 26.00 27.00 27.00 100.00 110.00 10.00
96 25.00 24.00 20.00 39.00 49.00 10.00
97 22.00 27.00 11.00 135.00 145.00 10.00
98 25.00 21.00 12.00 133.00 143.00 10.00
99 19.00 21.00 10.00 58.00 68.00 10.00
100 20.00 26.00 9.00 83.00 93.00 10.00
101 18.00 18.00 17.00 185.00 195.00 10.00
其他APS高级计划排程系统相关扩展阅读：
3、 APS演绎饭局模型（通俗的告诉您为什么ERP计划与APS计划的区别）
4、烽火集团PCBA企业应用云筹优化APS实现智能计划排产案例
7、云筹优化高级计划排程Light版助力中小企业实现精益化计划
9、云筹优化APS混合遗传算法求解FJSP柔性车间调度最优化问题
此内容由惯性聚合(RSS阅读器)自动聚合整理，仅供阅读参考。 原文来自 — 版权归原作者所有。