车辆路线问题(VRP)最早是由Dantzig和Ramser于1959年首次提出，它是指一定数量的客户，各自有不同数量的货物需求，配送中心向客户提供货物，由一个车队负责分送货物，组织适当的行车路线，目标是使得客户的需求得到满足，并能在一定的约束下，达到诸如路程最短、成本最小、耗费时间最少等目的。
VRP问题有很多子问题：
- the capacitated vehicle routing problem (CVRP) , 即classical VRP
- the vehicle routing problem with time windows (VRPTW) , 带时间窗 - VRPHTW 硬时间窗 ｜ VRPSTW 软时间窗 ｜ VRPTD(VRP with Time Deadlines)带顾客最迟服务时间
- the Multiple Depot Vehicle Routing Problem (MDVRP) , 多车场
- the Period Vehicle Routing Problem (PVRP) , 周期车辆路径问题
一般使用精确算法 或 启发式算法
- 精确算法适用于小规模问题，能得到最优解。
- direct tree search , 直接树搜索 | dynamic programming , 动态规划 | integer linear programming , 整数线性规划
- 启发式算法用于大规模问题，能快速找出可行解。
- Simulated Annealing 模拟退火
- Tabu Search 禁忌搜索
- Genetic Algoritm 遗传算法 | Genetic Programming 遗传规划
- Genetic Network Programming 遗传网络规划
- ACS, Ant Colony System 蚁群算法
我主要是研究了蚁群算法和CW节约算法，发现后者思路比较清晰，并且我们项目的需求也不复杂，所以基于后者的思想来实现。
考虑这样的需求：
某集散中心管辖10个邮局，已知集散中心和各营业点的经纬度，寄达各支局和各支局收寄的邮件， 时间窗口。
邮车装载邮件数不同。邮车的运行成本为3元/公里， 速度为30km每小时。试用最少邮车，并规划邮车的行驶路线使总费用最省。
那么输入参数需要包括：
- 各个节点的经纬度，邮件收寄数，邮件送达数，时间窗(如果有要求的话，包括最早、最晚到达时间)，装卸货时间
- 可用车辆的载重
输出结果就是算法形成的路径，每条路径中包括到达邮局的先后次序。
目前已经基于CW节约算法，实现 载重量 约束 以及 时间窗口约束，使用Java作为实现。
邮局类
1 package vrp; 2 3 import java.util.Objects; 4 5 /** 6 * @author 陈海越 7 * @version 1.0 8 * @since 新标准版5.0 9 */ 10 public class PostOffice implements Cloneable { 11 12 public PostOffice(int index, String name, float x, float y, 13 float receive, float sendOut, 14 int earliestTime, int latestTime, int duration, 15 int type) { 16 this.index = index; 17 this.name = name; 18 this.x = x; 19 this.y = y; 20 this.receive = receive; 21 this.sendOut = sendOut; 22 this.earliestTime = earliestTime; 23 this.latestTime = latestTime; 24 this.duration = duration; 25 this.type = type; 26 } 27 28 /** 29 * 序号 30 */ 31 private int index; 32 33 private String name; 34 35 private float x; 36 37 private float y; 38 39 private float receive; 40 41 private float sendOut; 42 43 /** 44 * 最早到达时间 45 */ 46 private int earliestTime; 47 48 /** 49 * 最晚到达时间 50 */ 51 private int latestTime; 52 53 /** 54 * 到达时间 55 */ 56 private int arrivedTime; 57 58 private int duration; 59 60 private int type; 61 62 private Route currentRoute; 63 64 private PostOffice previousNode; 65 66 private PostOffice nextNode; 67 68 public String getName() { 69 return name; 70 } 71 72 public void setName(String name) { 73 this.name = name; 74 } 75 76 public float getSendOut() { 77 return sendOut; 78 } 79 80 public void setSendOut(float sendOut) { 81 this.sendOut = sendOut; 82 } 83 84 public PostOffice getPreviousNode() { 85 return previousNode; 86 } 87 88 public void setPreviousNode(PostOffice previousNode) { 89 this.previousNode = previousNode; 90 } 91 92 public PostOffice getNextNode() { 93 return nextNode; 94 } 95 96 public void setNextNode(PostOffice nextNode) { 97 this.nextNode = nextNode; 98 } 99 100 public int getArrivedTime() {101 return arrivedTime;102 }103 104 public void setArrivedTime(int arrivedTime) {105 this.arrivedTime = arrivedTime;106 }107 108 109 public Route getCurrentRoute() {110 return currentRoute;111 }112 113 public void setCurrentRoute(Route currentRoute) {114 this.currentRoute = currentRoute;115 }116 117 public int getIndex() {118 return index;119 }120 121 public float getX() {122 return x;123 }124 125 public float getY() {126 return y;127 }128 129 public float getReceive() {130 return receive;131 }132 133 public int getEarliestTime() {134 return earliestTime;135 }136 137 public int getLatestTime() {138 return latestTime;139 }140 141 public int getDuration() {142 return duration;143 }144 145 public int getType() {146 return type;147 }148 149 public float distanceTo(PostOffice p2) {150 return distanceTo(y, x, p2.y, p2.x, 'K');151 }152 153 /**154 * 使用经纬度计算，返回距离155 * @param lat1 纬度1156 * @param lon1 经度1157 * @param lat2 纬度2158 * @param lon2 经度2159 * @param unit 'K' 公里 ，默认 英里160 * @return161 */162 private float distanceTo(double lat1, double lon1, double lat2, double lon2, char unit) {163 double theta = lon1 - lon2;164 double dist = Math.sin(deg2rad(lat1)) * Math.sin(deg2rad(lat2)) + Math.cos(deg2rad(lat1)) * Math.cos(deg2rad(lat2)) * Math.cos(deg2rad(theta));165 dist = Math.acos(dist);166 dist = rad2deg(dist);167 dist = dist * 60 * 1.1515;168 if (unit == 'K') {169 dist = dist * 1.609344;170 }171 return (float)(dist);172 }173 174 private double deg2rad(double deg) {175 return (deg * Math.PI / 180.0);176 }177 178 private double rad2deg(double rad) {179 return (rad * 180.0 / Math.PI);180 }181 182 public int getDepartTime() {183 return arrivedTime + duration;184 }185 186 @Override187 public boolean equals(Object o) {188 if (this == o) return true;189 if (o == null || getClass() != o.getClass()) return false;190 PostOffice that = (PostOffice) o;191 return Float.compare(that.x, x) == 0 &&192 Float.compare(that.y, y) == 0;193 }194 195 @Override196 public String toString() {197 return "PostOffice{" + index +198 " (" + x +199
| 
转播
