禁忌搜索算法求解取送货问题

禁忌搜索算法求解PDP取送货问题
订单信息是商家-顾客对，分别有编号、x，y坐标、需求、时间窗、服务时间的属性
算例为50对订单，0为配送中心、1-25为顾客、26-51为商家
优化目标为：行驶路程+超时时间最小
readin()读取数据，初始化订单
Construction（）贪心策略生成初始路径、初始解
shift（）移位算子，进行邻域搜索

#include <iostream>
#include <fstream>
#include <math.h>
#include <vector>
#include <ctime>
#include <cstdlib>

using namespace std;

#define Number 50
#define road_number 10
#define Iteration 500
#define Capacity 40
#define tensure 30
/*******************************************************************************/
//变量
double Value_gol = 0x3ffffff;   //全局最优解

double Distance[Number+1][Number+1];  //距离矩阵

int tabu[Number+1][Number+1];  //禁忌表
/*******************************************************************************/
//节点类
class Customer{
 public:
    double x,y,demand; //坐标，需求
    double early,last,ser;    //时间窗上下限、服务时长
    int id,r;            //节点号
    Customer()
    {

    }
    void read(int i,double x1,double y1,double d,int e,int l,int s){
        x = x1,y = y1,early = e,last = l,id = i,demand = d,ser = s;
    }
};
Customer *customer = new Customer[Number+1];
/*******************************************************************************/
//路径类
class Road{
 public:
     int id;//路径的编号
     double subt,dis; //路径的超时、路程
     vector<Customer> R;//节点容器
    Road(){

    }
    void subtime();  //计算超时时长
    int dist();  //计算行驶距离
};
Road *road = new Road[road_number];
Road *road_final = new Road[road_number];  //保存最优路径
/*******************************************************************************/
//计算路径超时时间
void Road::subtime()
{
    subt = 0;
    double Arrivetime = 0;
    for(int i = 1; i < R.size(); ++i){
        Arrivetime += Distance[R[i].id][R[i-1].id];
        if(Arrivetime > R[i].last)
            subt += Arrivetime - R[i].last;
        else if(Arrivetime < R[i].early)
            Arrivetime = R[i].early;
    }
}
//计算路程
int Road::dist()
{
    dis = 0;
    int bag = 0;
    for(int i = 1; i < R.size(); ++i){
        dis += Distance[R[i-1].id][R[i].id];
        bag += R[i].demand;
        if(bag > Capacity)
            return -1;
    }
    return 1;
}
/*******************************************************************************/
// 读入节点数据，初始化节点、初始化路径、初始化距离矩阵、初始化禁忌表
void readin()
{
    fstream file;
    file.open("R101.txt");
    double temp[7];
    for(int i = 0; i <= Number; ++i){
        for(int j = 0; j < 7; ++j){
             file >> temp[j];
        }
        if(i <= Number/2)
           customer[i].read(i,temp[1],temp[2],temp[3],temp[4],temp[5],temp[6]);
        else
           customer[i].read(i,temp[1],temp[2],-temp[3],temp[4],temp[5],temp[6]);
    }
    file.close();

    for(int i = 0; i < road_number; ++i){            //初始化路径
        road[i].id = i,road[i].subt = road[i].dis = 0;
        road[i].R.push_back(customer[0]);
        road[i].R.push_back(customer[0]);
        road[i].R[0].last = road[i].R[0].early;
        road[i].R[1].early = road[i].R[1].last;
    }

    for(int i = 0; i <= Number; ++i)
        for(int j = 0; j <= Number; ++j){
            Distance[i][j] = sqrt(pow(customer[i].x-customer[j].x,2)+pow(customer[i].y-customer[j].y,2));
    }

    for(int i = 0; i <= Number; ++i)
        for(int j = 0; j <= Number; ++j){
            tabu[i][j] = 0;
    }
}
/*******************************************************************************/
//生成初始路径
void Construction()
{
    int cur = 0;   //当前路径数
    int n = Number/2;   //商家顾客偏移值
    double temp1,temp2;
    vector<Customer> C;
    for(int i = 1; i <= Number/2; ++i)
        C.insert(C.begin(),customer[i]);
    while(C.size() > 0){
         int besti,bestj;
         double Value = 0x3fffffff;
         int k = rand()%C.size();
         int id = C[k].id;
         C.erase(C.begin()+k);
         int r = rand()%road_number;
         if(r > cur) r = cur+1,cur++;
         for(int i = 1; i < road[r].R.size(); ++i){
            road[r].R.insert(road[r].R.begin()+i,customer[id+n]);
            for(int j = i+1; j < road[r].R.size(); ++j){
                road[r].R.insert(road[r].R.begin()+j,customer[id]);
                int flag = road[r].dist();
                if(flag == 1){
                    road[r].subtime();
                    if(road[r].dis+road[r].subt < Value){
                        Value = road[r].dis+road[r].subt;
```cpp
                        besti = i,bestj = j;
                        temp1 = road[r].dis,temp2 = road[r].subt;
                    }
                }
                road[r].R.erase(road[r].R.begin()+j);
            }
            road[r].R.erase(road[r].R.begin()+i);
         }
         road[r].R.insert(road[r].R.begin()+besti,customer[id+n]);
         road[r].R.insert(road[r].R.begin()+bestj,customer[id]);
         road[r].dis = temp1,road[r].subt = temp2;
         customer[id+n].r = customer[id].r = r;
    }
    Value_gol = 0;
    for(int i = 0; i < road_number; ++i){             //计算成本
        if(road[i].R.size() > 1)
        Value_gol += road[i].subt + road[i].dis;
    }
}
/*******************************************************************************/
//输出路径
void output(Road *road)
{
    int j = 1;
    for(int i = 0; i < road_number; ++i){
        if(road[i].R.size() > 2){
            cout << "NO." << j++ <<":";
            for(int j = 0; j < road[i].R.size() ; ++j)
                cout << road[i].R[j].id << "->";
            cout << endl;
        }
    }
}
/*******************************************************************************/
//移位算子
void shift(int iteration)
{
    double Value_cur = 0x3fffffff,V = 0;
    for(int i = 0; i < road_number; ++i){
        if(road[i].R.size() > 2)
        V += road[i].subt + road[i].dis;
    }
    int n = Number/2;   //商家顾客偏移值
    int r = 0,formeri,formerj,besti,bestj,bestr,bestc;   //节点所在路径、节点原先的位置、节点最佳插入点
    for(int k = 1; k <=Number/2; ++k){
        r = customer[k].r;
        for(int x = 1; x < road[r].R.size(); ++x){
            if(road[r].R[x].id == k+n)
                formeri = x;                //找到选取订单节点的位置besti、bestj
            if(road[r].R[x].id == k){
                formerj = x;
                break;
            }
        }
        road[r].R.erase(road[r].R.begin() + formerj);
        road[r].R.erase(road[r].R.begin() + formeri);
        //在邻域开始搜索候选解
        double temp1 = road[r].subt,temp2 = road[r].dis;
        for(int y = 0; y < road_number; ++y)    //y选择插入的路径
           if(y != r && tabu[k][y] < iteration){
              double Value = 0,Dist;
              double temp3 = road[y].subt,temp4 = road[y].dis;
              for(int i = 1; i < road[y].R.size(); ++i){
                road[y].R.insert(road[y].R.begin() + i,customer[k+n]);
                for(int j = i+1; j < road[y].R.size(); ++j){
                    road[y].R.insert(road[y].R.begin() + j,customer[k]);
                    Value = V - temp1 - temp2 - temp3 - temp4;
                    Dist = road[y].dist();
                    if(Dist != -1){
                        road[r].dist(),road[r].subtime();
                        road[y].subtime();
                        Value +=  road[r].dis + road[r].subt + road[y].dis + road[y].subt;
                        if(Value < Value_cur){
                            Value_cur = Value;
                            besti = i,bestj = j,bestr = y,bestc = k;  //记录最优候选解的信息
                        }
                    }
                    road[y].subt = temp3,road[y].dis = temp4;
                    road[y].R.erase(road[y].R.begin() + j);
                }
                road[y].R.erase(road[y].R.begin() + i);
              }
           }
        road[r].subt = temp1,road[r].dis =temp2;
        road[r].R.insert(road[r].R.begin() + formeri,customer[k+n]);
        road[r].R.insert(road[r].R.begin() + formerj,customer[k]);
    }
    r = customer[bestc].r;
    for(int x = 1; x < road[r].R.size(); ++x){
        if(road[r].R[x].id == bestc+n)
            formeri = x;                //找到选取订单节点的位置
        if(road[r].R[x].id == bestc)
            formerj = x;
    }
    road[r].R.erase(road[r].R.begin() + formerj);           //进行候选解插入
    road[r].R.erase(road[r].R.begin() + formeri);
    road[bestr].R.insert(road[bestr].R.begin() + besti,customer[bestc+n]);
    road[bestr].R.insert(road[bestr].R.begin() + bestj,customer[bestc]);
    road[bestr].R[besti].r = road[bestr].R[bestj].r = bestr;
    customer[bestc+n].r = customer[bestc].r = bestr;
    road[r].dist(),road[r].subtime();
    road[bestr].dist(),road[bestr].subtime();
    if(Value_cur < Value_gol){
        Value_gol = Value_cur;
        for(int i = 0; i < road_number; ++i)
            road_final[i] = road[i];            //把全局最优解记录到road_final
    }
    tabu[bestc][bestr] = iteration + rand()%10 + tensure;   //更新禁忌表
    cout << iteration << "  " << Value_cur << endl;
}
/*******************************************************************************/
int main()
{
    srand((int)time(0));
    readin();    //读取数据
    output(road);
    Construction();   //生成初始解
    output(road);
    int i = 1;
    while( i <= Iteration){    //迭代搜索
        shift(i);
        i++;
    }
    cout << endl << Value_gol <<endl;
    output(road_final);   //输出最优路径
    system("pause");
    return 0;
}
/*************测试数据**************/
1  15  15  0  0  300  0
2  8  3  3  205  217  1
3  23  24  3  59  79  1
4  23  14  6  103  123  1
5  23  5  5  35  51  1
6  26  28  2  97  114  1
7  15  5  3  117  134  1
8  5  26  1  199  216  1
9  5  18  3  127  139  1
10  5  4  9  36  46  1
11  29  15  3  220  239  1
12  25  23  8  42  53  1
13  25  26  4  113  127  1
14  16  17  4  71  86  1
15  9  19  8  112  130  1
16  22  19  3  201  216  1
17  14  17  4  37  53  1
18  12  19  7  149  163  1
19  8  26  7  29  39  1
20  7  12  4  124  142  1
21  18  12  9  144  161  1
22  3  5  8  217  232  1
23  10  22  2  141  160  1
24  15  5  6  76  90  1
25  7  12  8  53  68  1
26  28  0  1  104  114  1
27  13  10  0  179  196  0
28  5  2  0  27  42  0
29  27  24  0  90  104  0
30  28  3  0  14  27  0
31  14  26  0  62  74  0
32  28  29  0  92  102  0
33  13  1  0  188  198  0
34  21  29  0  98  112  0
35  29  26  0  14  28  0
36  23  26  0  199  218  0
37  14  27  0  17  35  0
38  29  26  0  87  103  0
39  27  2  0  48  63  0
40  9  16  0  83  102  0
41  25  26  0  190  207  0
42  22  6  0  17  29  0
43  22  19  0  128  139  0
44  8  22  0  16  27  0
45  0  24  0  109  124  0
46  28  9  0  120  140  0
47  13  7  0  196  209  0
48  6  16  0  110  120  0
49  27  16  0  42  62  0
50  16  23  0  33  50  0
51  10  19  0  83  95  0