欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

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

程序员文章站 2022-05-20 20:26:30
...

禁忌搜索算法求解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