前面讲了Cplex直接求解VRPTW的模型，下面我们在分支定界算法中调用Cplex来求解VRPTW
1、分支定界算法
（1）定义：
（2）求解过程：
1）确定一个下界（初始解LB），上界定为无穷大UB
2）把初始问题构建一个节点加入优先队列
3) 判断队列是否为空，如果为空跳转至7，否则取出并弹出队首元素，计算该节点的目标值P
4) 如果P > UB，返回3。否则判断当前节点是否是合法解（对于任意i,j,k,x_ijk均为整数），如果是，跳转5否则跳转6
5) 如果P < UB, 记录UB = P，当前节点为当前最优解BS。返回3
6) 设置两个子节点L, R。L，R的建立方式如上，如果L的目标值L.P <= UB，把L加入队列，如果R的目标值R.P <= UB，把R加入队列。返回3
7) 结束，返回记录的最优节点BS。如果BS为空则无解
2、分支定界求解VRPTW
代码结构如下
Data类的作用是定义变量、变量初始化、读取数据
package com.chb;
import java.io.BufferedReader;
import java.io.FileReader;
import java.util.Scanner;
//定义参数
class Data{
public static final double gap= 1e-6;
public static final double big_num = 100000;
public static int pointnum=102; //所有点集合n（包括配送中心和客户点，首尾（0和n）为配送中心）
public static double E; //配送中心时间窗开始时间
public static double L; //配送中心时间窗结束时间
public static int carnum; //车辆数
public static double cap; //车辆载荷
public static int[][] point=new int[pointnum][2];; //所有点的坐标x,y
public static int[] demand=new int[pointnum]; //需求量
public static int[] car=new int[carnum]; //车辆编号
public static double[] a=new double[pointnum]; //时间窗开始时间【a[i],b[i]】
public static double[] b=new double[pointnum]; //时间窗结束时间【a[i],b[i]】
public static double[] s=new double[pointnum]; //客户点的服务时间
public static int[][] arcs=new int[pointnum][pointnum]; //arcs[i][j]表示i到j点的弧
public static double[][] dist=new double[pointnum][pointnum]; //距离矩阵，满足三角关系,暂用距离表示花费 C[i][j]=dist[i][j]
//截断小数3.26434-->3.2
public double double_truncate(double v){
int iv = (int) v;
if(iv+1 - v <= gap)
return iv+1;
double dv = (v - iv) * 10;
int idv = (int) dv;
double rv = iv + idv / 10.0;
return rv;
}
public Data() {
super();
}
//函数功能：从txt文件中读取数据并初始化参数
public void read_data(String path,Data data) throws Exception{
String line = null;
String[] substr = null;
Scanner cin = new Scanner(new BufferedReader(new FileReader(path))); //读取文件
//读取1-4行
for(int i =0; i < 4;i++){
line = cin.nextLine();
}
//读取5行
line = cin.nextLine();
line.trim();
substr = line.split(("\\s+"));
carnum = Integer.parseInt(substr[1]);
cap = Integer.parseInt(substr[2]);
//读取6-9行
for(int i =0; i < 4;i++){
line = cin.nextLine();
}
//读取pointnum-1行数据
for (int i = 0; i < pointnum - 1; i++) {
line = cin.nextLine();
line.trim();
substr = line.split("\\s+");
point[i][0] = Integer.parseInt(substr[2]);
point[i][1] = Integer.parseInt(substr[3]);
demand[i] = Integer.parseInt(substr[4]);
a[i] = Integer.parseInt(substr[5]);
b[i] = Integer.parseInt(substr[6]);
s[i] = Integer.parseInt(substr[7]);
}
cin.close();//关闭流
//初始化终点参数
point[pointnum-1] = point[0];
demand[pointnum-1] = 0;
a[pointnum-1] = a[0];
b[pointnum-1] = b[0];
E = a[0];
L = b[0];
s[pointnum-1] = 0;
double min1 = 1e15;
double min2 = 1e15;
//距离矩阵初始化
for (int i = 0; i < pointnum; i++) {
for (int j = 0; j < pointnum; j++) {
if (i == j) {
dist[i][j] = 0;
continue;
}
dist[i][j] =
Math.sqrt(Math.pow(point[i][0]-point[j][0], 2)+Math.pow(point[i][1]-point[j][1], 2));
dist[i][j]=double_truncate(dist[i][j]);
}
}
dist[0][pointnum-1] = 0;
dist[pointnum-1][0] = 0;
//距离矩阵满足三角关系
for (int k = 0; k < pointnum; k++) {
for (int i = 0; i < pointnum; i++) {
for (int j = 0; j < pointnum; j++) {
if (dist[i][j] > dist[i][k] + dist[k][j]) {
dist[i][j] = dist[i][k] + dist[k][j];
}
}
}
}
//初始化为完全图
for (int i = 0; i < pointnum; i++) {
for (int j = 0; j < pointnum; j++) {
if (i != j) {
arcs[i][j] = 1;
}
else {
arcs[i][j] = 0;
}
}
}
//除去不符合时间窗和容量约束的边
for (int i = 0; i < pointnum; i++) {
for (int j = 0; j < pointnum; j++) {
if (i == j) {
continue;
}
if (a[i]+s[i]+dist[i][j]>b[j] ||
demand[i]+demand[j]>cap) {
arcs[i][j] = 0;
}
if (a[0]+s[i]+dist[0][i]+dist[i][pointnum-1]>
b[pointnum-1]) {
System.out.println("the calculating example is false");
}
}
}
for (int i = 1; i < pointnum-1; i++) {
if (b[i] - dist[0][i] < min1) {
min1 = b[i] - dist[0][i];
}
if (a[i] + s[i] + dist[i][pointnum-1] < min2) {
min2 = a[i] + s[i] + dist[i][pointnum-1];
}
}
if (E > min1 || L < min2) {
System.out.println("Duration false!");
System.exit(0);//终止程序
}
//初始化配送中心0，n+1两点的参数
arcs[pointnum-1][0] = 0;
arcs[0][pointnum-1] = 1;
for (int i = 1; i < pointnum-1; i++) {
arcs[pointnum-1][i] = 0;
}
for (int i = 1; i < pointnum-1; i++) {
arcs[i][0] = 0;
}
}
}
Node类的主要作用是记录分支节点
package com.chb;
import java.util.ArrayList;
public class Node implements Comparable{
Data data;
int d;
double node_cost; //目标值object
double[][][]lp_x;//记录lp解
int[][][] node_x_map;//node_xij=1时,node_x_mapijk=1表示必须访问，node_x_mapijk=0表示不能访问
int[][] node_x;//0表示弧可以访问，1表示必须访问，-1表示不能访问
ArrayList<ArrayList<Integer>> node_routes; //定义车辆路径链表
ArrayList<ArrayList<Double>> node_servetimes; //定义花费时间链表
public Node(Data data) {
super();
this.data = data;
node_cost = data.big_num;
lp_x = new double [data.pointnum][data.pointnum][data.carnum];
node_x_map = new int[data.pointnum][data.pointnum][data.carnum];
node_x = new int[data.pointnum][data.pointnum];
node_routes = new ArrayList<ArrayList<Integer>>();
node_servetimes = new ArrayList<ArrayList<Double>>();
}
//复制node
@SuppressWarnings("unchecked")
public Node note_copy() {
Node new_node = new Node(data);
new_node.d = d;
new_node.node_cost = node_cost;
for (int i = 0; i < lp_x.length; i++) {
for (int j = 0; j < lp_x[i].length; j++) {
new_node.lp_x[i][j] = lp_x[i][j].clone();
}
}
for (int i = 0; i < node_x.length; i++) {
new_node.node_x[i] = node_x[i].clone();
}
for (int i = 0; i < node_x_map.length; i++) {
for (int j = 0; j < node_x_map[i].length; j++) {
new_node.node_x_map[i][j] = node_x_map[i][j].clone();
}
}
for (int i = 0; i < node_routes.size(); i++) {
new_node.node_routes.add((ArrayList<Integer>) node_routes.get(i).clone());
}
for (int i = 0; i < node_servetimes.size(); i++) {
new_node.node_servetimes.add((ArrayList<Double>) node_servetimes.get(i).clone());
}
return new_node;
}
public int compareTo(Object o){
Node node = (Node) o;
if(node_cost < node.node_cost)
return -1;
else if(node_cost == node.node_cost)
return 0;
else
return 1;
}
}
BaB_Vrptw类是程序的主函数，其中
init() 这个函数的作用是确定有合法解的最小车辆数量,具体的做法就是建立一个松弛了的cplex模型，并计算使用的车辆数，如果有aa辆未使用车辆就减少aa辆可用车辆，否则减少一辆直到没有可行解。当然，最后我们可使用的车辆是最少的车辆，松弛的模型就是把前面模型把中的x_ijk的整数约束去掉得到的
branch and bound过程：把VRPTW的数学模型松弛的成一个线性规划问题可以求解出VRPTW问题的一个下界，分支的原则就是对于一个选定的x_ijk，且0<x_ijk<1，那么，利用这个x_ijk进行分成两支，左支是不能够走弧ij，右支是必须走弧ij且必须由车辆k经过。即左支对于任意的t，x_ijt = 0。右边则是x_ijk = 1，通过find_arc() 函数找到要分支的弧
package com.chb;
import java.util.ArrayList;
import java.util.PriorityQueue;
import ilog.concert.IloException;
import ilog.concert.IloNumExpr;
import ilog.concert.IloNumVar;
import ilog.concert.IloNumVarType;
import ilog.cplex.IloCplex;
//类功能：建立模型并求解
public class BaB_Vrptw {
Data data; //定义类Data的对象
Node node1;
Node node2;
int deep;//深度
public PriorityQueue<Node> queue;//分支队列
Node best_note;//当前最好分支
double cur_best;//最好解
int []record_arc;//记录需要分支的节点
double x_gap;//很小的数
IloCplex model; //定义cplex内部类的对象
public IloNumVar[][][] x; //x[i][j][k]表示弧arcs[i][j]被车辆k访问
public IloNumVar[][] w; //车辆访问所有点的时间矩阵
double cost; //目标值object
double[][][] x_map;//cplex参数x
ArrayList<ArrayList<Integer>> routes; //定义车辆路径链表
ArrayList<ArrayList<Double>> servetimes; //定义花费时间链表
public BaB_Vrptw(Data data) {
this.data = data;
x_gap = data.gap;
routes = new ArrayList<>(); //定义车辆路径链表
servetimes = new ArrayList<>(); //定义花费时间链表
//初始化车辆路径和花费时间链表，链表长度为车辆数k
for (int k = 0; k < data.carnum; k++) {
ArrayList<Integer> r = new ArrayList<>();
ArrayList<Double> t = new ArrayList<>();
routes.add(r);
servetimes.add(t);
}
x_map = new double[data.pointnum][data.pointnum][data.carnum];
}
public void clear_lp() {
data=null;
routes.clear();
servetimes.clear();
x_map=null;
}
//辅助lp解到node
@SuppressWarnings("unchecked")
public void copy_lp_to_node(BaB_Vrptw lp, Node node) {
node.node_routes.clear();
node.node_servetimes.clear();
node.node_cost = lp.cost;
for (int i = 0; i < lp.x_map.length; i++) {
for (int j = 0; j < lp.x_map[i].length; j++) {
node.lp_x[i][j] = lp.x_map[i][j].clone();
}
}
for (int i = 0; i < lp.routes.size(); i++) {
node.node_routes.add((ArrayList<Integer>) lp.routes.get(i).clone());
}
for (int i = 0; i < lp.servetimes.size(); i++) {
node.node_servetimes.add((ArrayList<Double>) lp.servetimes.get(i).clone());
}
}
//函数功能：根据VRPTW数学模型建立VRPTW的cplex模型
//建立模型
private void build_model() throws IloException {
//model
model = new IloCplex();
model.setOut(null);
// model.setParam(IloCplex.DoubleParam.EpOpt, 1e-9);
// model.setParam(IloCplex.DoubleParam.EpGap, 1e-9);
//variables
x = new IloNumVar[data.pointnum][data.pointnum][data.carnum];
w = new IloNumVar[data.pointnum][data.carnum]; //车辆访问点的时间
//定义cplex变量x和w的数据类型及取值范围
for (int i = 0; i < data.pointnum; i++) {
for (int k = 0; k < data.carnum; k++) {
w[i][k] = model.numVar(0, 1e15, IloNumVarType.Float, "w" + i + "," + k);
}
for (int j = 0; j < data.pointnum; j++) {
if (data.arcs[i][j]==0) {
x[i][j] = null;
}
else{
//Xijk,公式(10)-(11)
for (int k = 0; k < data.carnum; k++) {
x[i][j][k] = model.numVar(0, 1, IloNumVarType.Float, "x" + i + "," + j + "," + k);
}
}
}
}
//加入目标函数
//公式(1)
IloNumExpr obj = model.numExpr();
for(int i = 0; i < data.pointnum; i++){
for(int j = 0; j < data.pointnum; j++){
if (data.arcs[i][j]==0) {
continue;
}
for(int k = 0; k < data.carnum; k++){
obj = model.sum(obj, model.prod(data.dist[i][j], x[i][j][k]));
}
}
}
model.addMinimize(obj);
//加入约束
//公式(2)
for(int i= 1; i < data.pointnum-1;i++){
IloNumExpr expr1 = model.numExpr();
for (int k = 0; k < data.carnum; k++) {
for (int j = 1; j < data.pointnum; j++) {
if (data.arcs[i][j]==1) {
expr1 = model.sum(expr1, x[i][j][k]);
}
}
}
model.addEq(expr1, 1);
}
//公式(3)
for (int k = 0; k < data.carnum; k++) {
IloNumExpr expr2 = model.numExpr();
for (int j = 1; j < data.pointnum; j++) {
if (data.arcs[0][j]==1) {
expr2 = model.sum(expr2, x[0][j][k]);
}
}
model.addEq(expr2, 1);
}
//公式(4)
for (int k = 0; k < data.carnum; k++) {
for (int j = 1; j < data.pointnum-1; j++) {
IloNumExpr expr3 = model.numExpr();
IloNumExpr subExpr1 = model.numExpr();
IloNumExpr subExpr2 = model.numExpr();
for (int i = 0; i < data.pointnum; i++) {
if (data.arcs[i][j]==1) {
subExpr1 = model.sum(subExpr1,x[i][j][k]);
}
if (data.arcs[j][i]==1) {
subExpr2 = model.sum(subExpr2,x[j][i][k]);
}
}
expr3 = model.sum(subExpr1,model.prod(-1, subExpr2));
model.addEq(expr3, 0);
}
}
//公式(5)
for (int k = 0; k < data.carnum; k++) {
IloNumExpr expr4 = model.numExpr();
for (int i = 0; i < data.pointnum-1; i++) {
if (data.arcs[i][data.pointnum-1]==1) {
expr4 = model.sum(expr4,x[i][data.pointnum-1][k]);
}
}
model.addEq(expr4, 1);
}
//公式(6)
double M = 1e5;
for (int k = 0; k < data.carnum; k++) {
for (int i = 0; i < data.pointnum; i++) {
for (int j = 0; j < data.pointnum; j++) {
if (data.arcs[i][j] == 1) {
IloNumExpr expr5 = model.numExpr();
IloNumExpr expr6 = model.numExpr();
expr5 = model.sum(w[i][k], data.s[i]+data.dist[i][j]);
expr5 = model.sum(expr5,model.prod(-1, w[j][k]));
expr6 = model.prod(M,model.sum(1,model.prod(-1, x[i][j][k])));
model.addLe(expr5, expr6);
}
}
}
}
//公式(7)
for (int k = 0; k < data.carnum; k++) {
for (int i = 1; i < data.pointnum-1; i++) {
IloNumExpr expr7 = model.numExpr();
for (int j = 0; j < data.pointnum; j++) {
if (data.arcs[i][j] == 1) {
expr7 = model.sum(expr7,x[i][j][k]);
}
}
model.addLe(model.prod(data.a[i], expr7), w[i][k]);
model.addLe(w[i][k], model.prod(data.b[i], expr7));
}
}
//公式(8)
for (int k = 0; k < data.carnum; k++) {
model.addLe(data.E, w[0][k]);
model.addLe(data.E, w[data.pointnum-1][k]);
model.addLe(w[0][k], data.L);
model.addLe(w[data.pointnum-1][k], data.L);
}
//公式(9)
for (int k = 0; k < data.carnum; k++) {
IloNumExpr expr8 = model.numExpr();
for (int i = 1; i < data.pointnum-1; i++) {
IloNumExpr expr9 = model.numExpr();
for (int j = 0; j < data.pointnum; j++) {
if (data.arcs[i][j] == 1) {
expr9=model.sum(expr9,x[i][j][k]);
}
}
expr8 = model.sum(expr8,model.prod(data.demand[i],expr9));
}
model.addLe(expr8, data.cap);
}
}
//函数功能：解模型，并生成车辆路径和得到目标值
//获取cplex解
public void get_value() throws IloException {
routes.clear();
servetimes.clear();
cost = 0;
// //初始化车辆路径和花费时间链表，链表长度为车辆数k
for (int k = 0; k < data.carnum; k++) {
ArrayList<Integer> r = new ArrayList<>();
ArrayList<Double> t = new ArrayList<>();
routes.add(r);
servetimes.add(t);
}
for (int i = 0; i < data.pointnum; i++) {
for (int j = 0; j < data.pointnum; j++) {
for (int k = 0; k < data.carnum; k++) {
x_map[i][j][k] = 0.0;
}
if (data.arcs[i][j]>0.5) {
for (int k = 0; k < data.carnum; k++) {
x_map[i][j][k]=model.getValue(x[i][j][k]);
}
}
}
}
//模型可解，生成车辆路径
for(int k = 0; k < data.carnum; k++){
boolean terminate = true;
int i = 0;
routes.get(k).add(0);
servetimes.get(k).add(0.0);
while(terminate){
for (int j = 0; j < data.pointnum; j++) {
if (doubleCompare(x_map[i][j][k], 0)==1) {
routes.get(k).add(j);
servetimes.get(k).add(model.getValue(w[j][k]));
i = j;
break;
}
}
if (i == data.pointnum-1) {
terminate = false;
}
}
}
cost = model.getObjValue();
}
//branch and bound过程
public void branch_and_bound(BaB_Vrptw lp) throws IloException {
cur_best = 3000;//设置上届
deep=0;
record_arc = new int[3];
node1 = new Node(data);
best_note = null;
queue = new PriorityQueue<Node>();
//初始解（非法解）
for (int i = 0; i < lp.routes.size(); i++) {
ArrayList<Integer> r = lp.routes.get(i);
System.out.println();
for (int j = 0; j < r.size(); j++) {
System.out.print(r.get(j)+" ");
}
}
lp.copy_lp_to_node(lp, node1);
// node1.node_cost = lp.cost;
// node1.lp_x = lp.x_map.clone();
// node1.node_routes =lp.routes;
// node1.node_servetimes = lp.servetimes;
node2 = node1.note_copy();
deep=0;
node1.d=deep;
queue.add(node1);
//branch and bound过程
while (!queue.isEmpty()) {
Node node = queue.poll();
//某支最优解大于当前最好可行解，删除
if (doubleCompare(node.node_cost, cur_best)>0) {
continue;
}else {
record_arc = lp.find_arc(node.lp_x);
//某支的合法解,0,1组合的解,当前分支最好解
if (record_arc[0]==-1) {
//比当前最好解好，更新当前解
if (doubleCompare(node.node_cost, cur_best)==-1) {
lp.cur_best = node.node_cost;
System.out.println(node.d+" cur_best:"+cur_best);
lp.best_note = node;
}
continue;
}else {//可以分支
node1 = lp.branch_left_arc(lp, node, record_arc);//左支
node2 = lp.branch_right_arc(lp, node, record_arc);//右支
if (node1!=null && doubleCompare(node1.node_cost, cur_best)<=0) {
queue.add(node1);
}
if (node2!=null && doubleCompare(node2.node_cost, cur_best)<=0) {
queue.add(node2);
}
}
}
}
}
//分支设置
public void set_bound(Node node) throws IloException {
for (int i = 0; i < data.pointnum; i++) {
for (int j = 0; j < data.pointnum; j++) {
if (data.arcs[i][j]>0.5) {
if (node.node_x[i][j]==0) {
for (int k = 0; k < data.carnum; k++) {
x[i][j][k].setLB(0.0);
x[i][j][k].setUB(1.0);
}
}else if (node.node_x[i][j]==-1) {
for (int k = 0; k < data.carnum; k++) {
x[i][j][k].setLB(0.0);
x[i][j][k].setUB(0.0);
}
}else {
for (int k = 0; k < data.carnum; k++) {
if (node.node_x_map[i][j][k]==1) {
x[i][j][k].setLB(1.0);
x[i][j][k].setUB(1.0);
}else {
x[i][j][k].setLB(0.0);
x[i][j][k].setUB(0.0);
}
}
}
}
}
}
}
public void set_bound1(Node node) throws IloException {
for (int i = 0; i < data.pointnum; i++) {
for (int j = 0; j < data.pointnum; j++) {
if (data.arcs[i][j]>0.5) {
for (int k = 0; k < data.carnum; k++) {
if (node.node_x_map[i][j][k]==0) {
x[i][j][k].setLB(0.0);
x[i][j][k].setUB(1.0);
}else if (node.node_x_map[i][j][k]==-1) {
x[i][j][k].setLB(0.0);
x[i][j][k].setUB(0.0);
}else {
x[i][j][k].setLB(1.0);
x[i][j][k].setUB(1.0);
}
}
}
}
}
}
//设置左支
public Node branch_left_arc(BaB_Vrptw lp,Node father_node,int[] record) throws IloException {
if (record[0] == -1) {
return null;
}
Node new_node = new Node(data);
new_node = father_node.note_copy();
new_node.node_x[record[0]][record[1]] = -1;
for (int k = 0; k < data.carnum; k++) {
new_node.node_x_map[record[0]][record[1]][k]=0;
}
// new_node.node_x_map[record[0]][record[1]][record[2]]=-1;
//设置左支
lp.set_bound(new_node);
if (lp.model.solve()) {
lp.get_value();
deep++;
new_node.d=deep;
lp.copy_lp_to_node(lp, new_node);
System.out.println(new_node.d+" "+lp.cost);
}else {
new_node.node_cost = data.big_num;
}
return new_node;
}
//设置右支
public Node branch_right_arc(BaB_Vrptw lp,Node father_node,int[] record) throws IloException {
if (record[0] == -1) {
return null;
}
Node new_node = new Node(data);
new_node = father_node.note_copy();
new_node.node_x[record[0]][record[1]] = 1;
// new_node.node_x_map[record[0]][record[1]][record[2]]=1;
for (int k = 0; k < data.carnum; k++) {
if (k==record[2]) {
new_node.node_x_map[record[0]][record[1]][k]=1;
}else {
new_node.node_x_map[record[0]][record[1]][k]=0;
}
}
//设置右支
lp.set_bound(new_node);
if (lp.model.solve()) {
lp.get_value();
deep++;
new_node.d=deep;
System.out.println(new_node.d+" right: "+lp.cost);
lp.copy_lp_to_node(lp, new_node);
}else {
new_node.node_cost = data.big_num;
}
return new_node;
}
//找到需要分支的支点位置
public int[] find_arc1(double[][][] x) {
int record[] = new int[3];//记录分支顶点
double cur_dif = 0;
double min_dif = Double.MAX_VALUE;
//找出最接近0.5的弧
for (int i = 1; i <data.pointnum-1; i++) {
for (int j = 1; j < data.pointnum-1; j++) {
if (data.arcs[i][j]>0.5) {
for (int k = 0; k <data.carnum; k++) {
//若该弧值为0或1，则继续
if (is_one_zero(x[i][j][k])) {
continue;
}
cur_dif = get_dif(x[i][j][k]);
if (doubleCompare(cur_dif, min_dif)==-1) {
record[0] = i;
record[1] = j;
record[2] = k;
min_dif = cur_dif;
}
}
}
}
}
//depot
if (doubleCompare(min_dif, Double.MAX_VALUE)==0) {
for (int i = 1; i < data.pointnum-1; i++) {
if (data.arcs[0][i]>0.5) {
for (int k = 0; k < data.carnum; k++) {
if (is_fractional(x[0][i][k])) {
cur_dif = get_dif(x[0][i][k]);
if (doubleCompare(cur_dif, min_dif)==-1) {
record[0] = 0;
record[1] = i;
record[2] = k;
min_dif = cur_dif;
}
}
}
}
if (data.arcs[i][data.pointnum-1]>0.5) {
for (int k = 0; k < data.carnum; k++) {
if (is_fractional(x[i][data.pointnum-1][k])) {
cur_dif = get_dif(x[i][data.pointnum-1][k]);
if (doubleCompare(cur_dif, min_dif)==-1) {
record[0] = i;
record[1] = data.pointnum-1;
record[2] = k;
min_dif = cur_dif;
}
}
}
}
}
}
if (doubleCompare(min_dif, data.big_num)==1) {
record[0] = -1;
record[1] = -1;
record[2] = -1;
}
return record;
}
// 找到要分支的弧
public int[] find_arc(double[][][] x) {
int record[] = new int[3];//记录分支顶点
for (int i = 0; i <data.pointnum; i++) {
for (int j = 0; j < data.pointnum; j++) {
if (data.arcs[i][j]>0.5) {
for (int k = 0; k <data.carnum; k++) {
//若该弧值为0或1，则继续
if (is_one_zero(x[i][j][k])) {
continue;
}
// cur_dif = get_dif(x[i][j][k]);
record[0] = i;
record[1] = j;
record[2] = k;
return record;
}
}
}
}
record[0] = -1;
record[1] = -1;
record[2] = -1;
return record;
}
//比较两个double数值的大小
public int doubleCompare(double a, double b){
if(a - b > x_gap)
return 1;
if(b - a > x_gap)
return -1;
return 0;
}
//判断是否为0到1之间的小数
public boolean is_fractional(double v){
if( v > (int) v + x_gap && v < (int) v + 1 - x_gap)
return true;
else
return false;
}
//判断是否为0或者1
public boolean is_one_zero(double temp) {
if (doubleCompare(temp, 0)==0 || doubleCompare(temp, 1)==0) {
return true;
}else {
return false;
}
}
//获取到0.5的距离
public double get_dif(double temp) {
double v = (int)temp+0.5;
if (v>temp) {
return v-temp;
} else {
return temp-v;
}
}
public BaB_Vrptw init(BaB_Vrptw lp) throws IloException {
lp.build_model();
if (lp.model.solve()) {
lp.get_value();
int aa=0;
for (int i = 0; i < lp.routes.size(); i++) {
if (lp.routes.get(i).size()==2) {
aa++;
}
}
System.out.println(aa);
if (aa==0) {
data.carnum -=1;
lp.model.clearModel();
lp = new BaB_Vrptw(data);
return init(lp);
}else {
data.carnum -=aa;
lp.model.clearModel();
lp = new BaB_Vrptw(data);
return init(lp);
}
}else {
data.carnum +=1;
System.out.println("vehicle number: "+data.carnum);
lp.model.clearModel();
lp = new BaB_Vrptw(data);
lp.build_model();
if (lp.model.solve()) {
lp.get_value();
return lp;
}else {
System.out.println("error init");
return null;
}
}
}
public static void main(String[] args) throws Exception {
Data data = new Data();
//读入不同的文件前要手动修改vetexnum参数，参数值等于所有点个数,包括配送中心
String path = "data/c102.txt";//算例地址
data.read_data(path,data);
System.out.println("input succesfully");
System.out.println("cplex procedure###########################");
BaB_Vrptw lp = new BaB_Vrptw(data);
double cplex_time1 = System.nanoTime();
//删除未用的车辆，缩小解空间
lp=lp.init(lp);
System.out.println(": "+lp.data.carnum);
lp.branch_and_bound(lp);
Check check = new Check(lp);
check.fesible();
double cplex_time2 = System.nanoTime();
double cplex_time = (cplex_time2 - cplex_time1) / 1e9;//求解时间，单位s
System.out.println("cplex_time " + cplex_time + " bestcost " + lp.cur_best);
for (int i = 0; i < lp.best_note.node_routes.size(); i++) {
ArrayList<Integer> r = lp.best_note.node_routes.get(i);
System.out.println();
for (int j = 0; j < r.size(); j++) {
System.out.print(r.get(j)+" ");
}
}
}
}
Check类的作用是检查解的可行性，包括解是否满足车辆数量约束，是否满足容量约束，时间窗约束等等
package com.chb;
import java.util.ArrayList;
import ilog.concert.IloException;
//类功能：解的可行性判断(可直接跳过此类)
class Check{
double epsilon = 0.0001;
Data data = new Data();
ArrayList<ArrayList<Integer>> routes = new ArrayList<>();
ArrayList<ArrayList<Double>> servetimes = new ArrayList<>();
public Check(BaB_Vrptw lp) {
super();
this.data = lp.data;
this.routes = lp.routes;
this.servetimes = lp.servetimes;
}
//函数功能：比较两个数的大小
public int double_compare(double v1,double v2) {
if (v1 < v2 - epsilon) {
return -1;
}
if (v1 > v2 + epsilon) {
return 1;
}
return 0;
}
//函数功能：解的可行性判断
public void fesible() throws IloException {
//车辆数量可行性判断
if (routes.size() > data.carnum) {
System.out.println("error: vecnum!!!");
System.exit(0);
}
//车辆载荷可行性判断
for (int k = 0; k < routes.size(); k++) {
ArrayList<Integer> route = routes.get(k);
double capasity = 0;
for (int i = 0; i < route.size(); i++) {
capasity += data.demand[route.get(i)];
}
if (capasity > data.cap) {
System.out.println("error: cap!!!");
System.exit(0);
}
}
//时间窗、车容量可行性判断
for (int k = 0; k < routes.size(); k++) {
ArrayList<Integer> route = routes.get(k);
ArrayList<Double> servertime = servetimes.get(k);
double capasity = 0;
for (int i = 0; i < route.size()-1; i++) {
int origin = route.get(i);
int destination = route.get(i+1);
double si = servertime.get(i);
double sj = servertime.get(i+1);
if (si < data.a[origin] && si > data.b[origin]) {
System.out.println("error: servertime!");
System.exit(0);
}
if (double_compare(si + data.dist[origin][destination],data.b[destination]) > 0) {
System.out.println(origin + ": [" + data.a[origin]
+ ","+data.b[origin]+"]"+ " "+ si);
System.out.println(destination + ": [" +
data.a[destination] + ","+data.b[destination]+"]"+ " "+ sj);
System.out.println(data.dist[origin][destination]);
System.out.println(destination + ":" );
System.out.println("error: forward servertime!");
System.exit(0);
}
if (double_compare(sj - data.dist[origin][destination],data.a[origin]) < 0) {
System.out.println(origin + ": [" + data.a[origin]
+ ","+data.b[origin]+"]"+ " "+ si);
System.out.println(destination + ": [" + data.a[destination]
+ ","+data.b[destination]+"]"+ " "+ sj);
System.out.println(data.dist[origin][destination]);
System.out.println(destination + ":" );
System.out.println("error: backward servertime!");
System.exit(0);
}
}
if (capasity > data.cap) {
System.out.println("error: cap!!!");
System.exit(0);
}
}
}
}
运行结果：
注：文本提炼、转载自
https://mp.weixin.qq.com/s?__biz=MzU0NzgyMjgwNg==&mid=2247484626&idx=1&sn=fa7ab4ea6e02084f4e8ed52c6c203eda&chksm=fb49c96bcc3e407db8c7bb9433dfb1fa787518328922bf061a4421c46557089b3429c9aeb391&mpshare=1&scene=1&srcid=0819ACkwrk90AoXHmuTfOewW&sharer_sharetime=1566189897645&sharer_shareid=054592193644de509623829748e83807&key=39e8dcac62579260153e141217c0c82d2c6e85d9ab908f37737e7a53942622438640915d71ffff9fcb2a13fe7ce9bddfcdfbd31c41de4e97aa05544e971a3b9da9c1048280222095be4e5c215e240a6b&ascene=1&uin=MjYzMDA1MzAyMQ%3D%3D&devicetype=Windows+10&version=62060834&lang=zh_CN&pass_ticket=XkzfvjtynhPBmAjeYlUVZf95yJsB8gJ7VNbzHQQ9yaInrn1wKsdFjIxND%2FyV40nF