运维开发网
广告位招商联系QQ:123077622
 
广告位招商联系QQ:123077622

用CPLEX求(VRPTW)带时间窗的车辆路径问题

运维开发网 https://www.qedev.com 2021-04-11 16:07 出处:51CTO 作者:mb5fd86d8699f84
.mod文件代码如下。  1/*****************************************************************************  2 *  3 * DATA  4 *  5 *****************************************************************************/  6  7

.mod文件代码如下。

 1/*****************************************************************************

 2 *

 3 * DATA

 4 *

 5 *****************************************************************************/

 6

 7// Vehicles

 8int     v          = ...;

 9range   Vehicles   = 1..v;

10

11// Customers

12int     CustomersNumber      = ...;

13range   Customers            = 1..CustomersNumber;

14range   CustomersAndDepots   = 0..(CustomersNumber+1); // includes the starting depot and the returning depot

15

16// Capacity

17int Capacity = ...;

18

19// Demand

20int Demand[Customers] = ...;

21

22// Time windows

23int LBTW[CustomersAndDepots] = ...; // Lower Bound of the Time Window

24int UBTW[CustomersAndDepots] = ...; // Upper Bound of the Time Window

25

26int   ServiceTime[CustomersAndDepots] = ...;

27int   XCoord[CustomersAndDepots] = ...;

28int   YCoord[CustomersAndDepots] = ...;

29float Distance[CustomersAndDepots][CustomersAndDepots]; // Cost or distance between i and j

30float Time[CustomersAndDepots][CustomersAndDepots]; // Cost or distance between i and j

31

32execute INITIALIZE {

33    for(var i in CustomersAndDepots) {

34        for (var j in CustomersAndDepots){

35            if (i == j) {

36                Distance[i][j] = 0;

37                Time[i][j] = 0;

38            } else {

39                Distance[i][j] = Math.floor(Math.sqrt(Math.pow(XCoord[i]-XCoord[j], 2) + Math.pow(YCoord[i]-YCoord[j], 2))*10)/10;

40                Time[i][j] = Distance [i][j] + ServiceTime[i];

41            }

42         }

43     }

44}

45

46// Decision variables

47dvar boolean x[Vehicles][CustomersAndDepots][CustomersAndDepots]; // 1 if a vehicle drives directly from vertex i to vertex j

48dvar int s[Vehicles][CustomersAndDepots]; // the time a vehicle starts to service a customer

49dexpr float maxTimeSpentBetweenTwoCustomers = max(a,b in CustomersAndDepots)(UBTW[a] + Time[a][b] - LBTW[b]);

50

51/*****************************************************************************

52 *

53 * MODEL

54 *

55 *****************************************************************************/

56minimize sum(k in Vehicles, i,j in CustomersAndDepots) (Distance[i][j]*x[k][i][j]);

57

58subject to {

59    forall(i in CustomersAndDepots, k in Vehicles)

60      x[k][i][i] == 0;

61

62       // Each customer is visited exactly once

63    forall (i in Customers)

64        sum(k in Vehicles, j in CustomersAndDepots) x[k][i][j] == 1;

65

66       // A vehicle can only be loaded up to it's capacity

67    forall(k in Vehicles)

68         sum(i in Customers, j in CustomersAndDepots)(Demand[i] * x[k][i][j]) <= Capacity;

69

70       // Each vehicle must leave the depot 0

71    forall(k in Vehicles)

72         sum (j in CustomersAndDepots)x[k][0][j] == 1;

73

74       // After a vehicle arrives at a customer it has to leave for another destination

75       forall(h in Customers, k in Vehicles)

76         sum(i in CustomersAndDepots)x[k][i][h] - sum(j in CustomersAndDepots)x[k][h][j] == 0;

77

78       // All vehicles must arrive at the depot n + 1

79       forall(k in Vehicles)

80         sum (i in CustomersAndDepots) x[k][i][CustomersNumber+1] == 1;

81

82       // The time windows are observed

83       forall(i in CustomersAndDepots, k in Vehicles)

84         LBTW[i] <= s[k][i] <= UBTW[i];

85

86       // From depot departs a number of vehicles equal to or smaller than v

87//       forall(k in Vehicles, j in CustomersAndDepots)

88         sum (k in Vehicles, j in CustomersAndDepots) x[k][0][j] <= v;

89

90       // Vehicle departure time from a customer and its immediate successor

91       forall(i,j in CustomersAndDepots, k in Vehicles)

92         s[k][i] + Time[i][j] - maxTimeSpentBetweenTwoCustomers*(1 - x[k][i][j]) <= s[k][j];

93};

94

95execute DISPLAY {

96    writeln("Solutions: ");

97    for(var k in Vehicles)

98        for(var i in CustomersAndDepots)

99            for (var j in CustomersAndDepots)

100                if(x[k][i][j] == 1)

101                    writeln("vehicle ", k, " from ", i, " to ", j);

102}

我想各位小伙伴对VRPTW的数学模型已经了熟于心了,下面对代码做一些解释:

7-30行是列出已知数据

32-44行计算出各个点之间的距离以及车辆在两个点之间需要行驶的时间

46-49行定义决策变量,其中maxTimeSpentBetweenTwoCustomers变量可以用一个大数进行替换,比如说定义成1e5

56行为目标函数,即使车辆行驶总距离最小

59-60行要求车辆不能在原地打转

62-64行要求每个顾客仅被访问一次

66-68行为容量限制约束,即每辆车的载重量不能超过容量限制

70-72行为每辆车必须从仓库0出发

74-76行为每辆车访问一个顾客后,必须前往下一个顾客

78-80行为所有车辆必须回到仓库n+1

82-84行为时间窗约束

86-88行要求使用的车辆数目必须小于等于初始在仓库车辆数目v

90-92行计算出在每个顾客的开始服务时间

95-102行打印出每辆车的所经过的顾客

上述代码求解的结果如下图所示:

用CPLEX求(VRPTW)带时间窗的车辆路径问题

车辆1路线:0-1-3-6

车辆2路线:0-6

车辆3路线:0-5-2-4-6

车辆4路线:0-6

车辆5路线:0-6

其中0和6代表仓库

数据文件.dat如下(各位如果想修改数据,可以修改此文件)

1v = 5;

2CustomersNumber = 5;

3Capacity = 200;

4

5Demand = #[

6    1: 10,

7    2: 7,

8    3: 13,

9    4: 19,

10    5: 26

11]#;

12

13ServiceTime = #[

14    0: 0,

15    1: 10,

16    2: 10,

17    3: 10,

18    4: 10,

19    5: 10,

20    6: 10

21]#;

22

23XCoord = #[

24    0: 35,

25    1: 41,

26    2: 35,

27    3: 55,

28    4: 55,

29    5: 15,

30    6: 65

31]#;

32

33YCoord = #[

34    0: 35,

35    1: 49,

36    2: 17,

37    3: 45,

38    4: 20,

39    5: 30,

40    6: 20

41]#;

42

43LBTW = #[

44    0: 0,

45    1: 0,

46    2: 0,

47    3: 0,

48    4: 0,

49    5: 0,

50    6: 0

51]#;

52

53UBTW = #[

54    0: 200,

55    1: 200,

56    2: 200,

57    3: 200,

58    4: 200,

59    5: 200,

60    6: 200

61]#;

各位小伙伴如果是刚开始学习CPLEX,可以CPLEX左上角文件-导入-现有OPL项目把文件导入进来,然后按以下操作步骤进行操作

用CPLEX求(VRPTW)带时间窗的车辆路径问题

扫码领视频副本.gif

0

精彩评论

暂无评论...
验证码 换一张
取 消

关注公众号