Tour planning

hello everyone,
The problem looks as follows:


There’re five consumers (location 2 to 6) and one depot (location 1) and the shortest distances between each other are given as follows:

from\to 1 2 3 4 5 6
1 0 30 20 22 28 34
2 30 0 28 38 20 14
3 20 28 0 10 8 14
4 22 38 10 0 18 24
5 28 20 8 18 0 6
6 34 14 14 24 6 0

Requirement:

  • The consumer 2 to m must be supplied by depot.
  • only one vehicle is be used, with a capacity of 4 units. and the load must not be over the capacity.
  • each consumer has a demand of 1 unit.
  • each tour should be begin and end with depot.
  • the distance of all the tours should be minimized.

thx for the help!


To view this discussion on the web visit https://groups.google.com/d/msg/gamsworld/-/4SO9G9UjKQ8J.
To post to this group, send email to gamsworld@googlegroups.com.
To unsubscribe from this group, send email to gamsworld+unsubscribe@googlegroups.com.
For more options, visit this group at http://groups.google.com/group/gamsworld?hl=en.

Hi servus126!

Here you get a model for tour planning with multiple vehicles and timewindows which works for me. Try to simplify the model for your problem by changing and deleting some restrictions.

In my include file the depot gets the index “depot” and is not, like all the other nodes, included in the subset customers(i).

I hope it will help you. Just let me know if you don’t understand a restriction.


set
k vehicles
i nodes
alias(i,j)
set customers(i) subset;


parameter
t(i,j) trip time from i to j
c(i,j) distance from i to j
d(i) demand of node i
cap(k) capacity of vehicle k
BigM BigM
Tmax max trip time
m amount of nodes
tf(i) earliest service time of i
ts(i) latest service time of i;

$include VRP.inc

parameter BigM BigM;
BigM = sum((i,j), t(i,j)+sz(i))+1;



variables Z objective function value;
binary variables x service variable;
binary variables y tourvariable;
positive variables w service time;
positive variable hv xxx;

Equations
Objective_function xxx
Restriction1(k) xxx
Restriction2(i,k) xxx
Restriction3(j,k) xxx
Restriction4(j) xxx
Restriction5(i,j) xxx
Restriction6(i,k) xxx
Restriction7(i) xxx
Restriction8(i) xxx
Restriction9(i,j,k) xxx
Restriction10(i,k) xxx
Restriction11 xxx
;

Objective_function…
Z =e= sum((i,j,k),c(i,j)*x(i,j,k));

Restriction1(k)…
sum(i, d(i)*y(i,k)) =l= cap(k);

Restriction2(i,k)…
sum(j, x(i,j,k)) =e= y(i,k);

Restriction3(j,k)…
sum(i, x(i,j,k)) =e= y(j,k);

Restriction4(i)$(customers(i))…
sum(k, y(i,k)) =e= 1;

Restriction5(i,j)$(customers(j) and customers(i) and ord(i)ord(j))…
hv(i)-hv(j)+ m*sum(k, x(i,j,k)) =l= m-1;

Restriction6(i,k)…
x(i,i,k) =e= 0;

Restriction7(i)$(customers(i))…
w(i) =g= tf(i);

Restriction8(i)$(customers(i))…
w(i) =l= ts(i);

Restriction9(i,j,k)$(customers(j) and ord(i)ord(j))…
w(j) =g= w(i) + sz(i) + t(i,j) - (1-x(i,j,k))*BigM;

Restriction10(i,k)$(customers(i))…
w(i) + sz(i) + t(i,‘depot’) - (1-x(i,‘depot’,k))*BigM =l= Tmax;

Restriction11…
w(‘dstart’)=e=0

\

To view this discussion on the web visit https://groups.google.com/d/msg/gamsworld/-/ohhYdRlKFTEJ.
To post to this group, send email to gamsworld@googlegroups.com.
To unsubscribe from this group, send email to gamsworld+unsubscribe@googlegroups.com.
For more options, visit this group at http://groups.google.com/group/gamsworld?hl=en.

Thanks a lot, Mathias.

What does variable hv represent? and could you please explain the restriction5 ? Thank you very much.

cheers,
servus126

在 2012年9月10日星期一UTC+2下午2时42分46秒,Mathias写道:

Hi servus126!

Here you get a model for tour planning with multiple vehicles and timewindows which works for me. Try to simplify the model for your problem by changing and deleting some restrictions.

In my include file the depot gets the index “depot” and is not, like all the other nodes, included in the subset customers(i).

I hope it will help you. Just let me know if you don’t understand a restriction.


set
k vehicles
i nodes
alias(i,j)
set customers(i) subset;


parameter
t(i,j) trip time from i to j
c(i,j) distance from i to j
d(i) demand of node i
cap(k) capacity of vehicle k
BigM BigM
Tmax max trip time
m amount of nodes
tf(i) earliest service time of i
ts(i) latest service time of i;

$include VRP.inc

parameter BigM BigM;
BigM = sum((i,j), t(i,j)+sz(i))+1;



variables Z objective function value;
binary variables x service variable;
binary variables y tourvariable;
positive variables w service time;
positive variable hv xxx;

Equations
Objective_function xxx
Restriction1(k) xxx
Restriction2(i,k) xxx
Restriction3(j,k) xxx
Restriction4(j) xxx
Restriction5(i,j) xxx
Restriction6(i,k) xxx
Restriction7(i) xxx
Restriction8(i) xxx
Restriction9(i,j,k) xxx
Restriction10(i,k) xxx
Restriction11 xxx
;

Objective_function…
Z =e= sum((i,j,k),c(i,j)*x(i,j,k));

Restriction1(k)…
sum(i, d(i)*y(i,k)) =l= cap(k);

Restriction2(i,k)…
sum(j, x(i,j,k)) =e= y(i,k);

Restriction3(j,k)…
sum(i, x(i,j,k)) =e= y(j,k);

Restriction4(i)$(customers(i))…
sum(k, y(i,k)) =e= 1;

Restriction5(i,j)$(customers(j) and customers(i) and ord(i)ord(j))…
hv(i)-hv(j)+ m*sum(k, x(i,j,k)) =l= m-1;

Restriction6(i,k)…
x(i,i,k) =e= 0;

Restriction7(i)$(customers(i))…
w(i) =g= tf(i);

Restriction8(i)$(customers(i))…
w(i) =l= ts(i);

Restriction9(i,j,k)$(customers(j) and ord(i)ord(j))…
w(j) =g= w(i) + sz(i) + t(i,j) - (1-x(i,j,k))*BigM;

Restriction10(i,k)$(customers(i))…
w(i) + sz(i) + t(i,‘depot’) - (1-x(i,‘depot’,k))*BigM =l= Tmax;

Restriction11…
w(‘dstart’)=e=0

\

To view this discussion on the web visit https://groups.google.com/d/msg/gamsworld/-/V7xcqXwo1UIJ.
To post to this group, send email to gamsworld@googlegroups.com.
To unsubscribe from this group, send email to gamsworld+unsubscribe@googlegroups.com.
For more options, visit this group at http://groups.google.com/group/gamsworld?hl=en.

Hi Servus,

Restriction 5 prevents shortcycles like in the picture below. hv is an “auxiliary variable” for that, which does’t have an important meaning for your result at the end.

\

To view this discussion on the web visit https://groups.google.com/d/msg/gamsworld/-/L2wFRpQM7CgJ.
To post to this group, send email to gamsworld@googlegroups.com.
To unsubscribe from this group, send email to gamsworld+unsubscribe@googlegroups.com.
For more options, visit this group at http://groups.google.com/group/gamsworld?hl=en.

Servus Michael! :wink:

Which restriction would you use for the problem od Servus?
I tried Restriction 1 to 6 but it doesn’t work.
Maybe I have a problem with the parameters or dynamic sets in the include file.


To view this discussion on the web visit https://groups.google.com/d/msg/gamsworld/-/a5cvBkndxMQJ.
To post to this group, send email to gamsworld@googlegroups.com.
To unsubscribe from this group, send email to gamsworld+unsubscribe@googlegroups.com.
For more options, visit this group at http://groups.google.com/group/gamsworld?hl=en.