Vehicle Routing Problem - How to Account for Time Windows?

[kevin.r...@gmail.com]

Hello Experts,

I am working on a VRPTW (Vehicle Routing Problem with Time Windows), based on a mathematical model that has already been created. I have a model file that should fulfill the requirements for a Vehicle Routing Problem with multiple vehicles, but I am unsure of how to specify the constraint that the whole quantity that the node requires must be delivered within a time window interval defined by [ai, bi]:

sik + d(i, j) − K(1 − xijk) sjk ∀(i, j ) ∈ A, ∀ k ∈ {1, . . . , K}, (8)

ai <= sik <= bi ∀i ∈ {1, . . . , N}, ∀ k ∈ {1, . . . , K}, (9)

These are the constraints that must be accounted for, given that sik/sjk is the time at which vehicle k reaches node i and j respectively, d(i, j) is the travel time from i to j, K is the number of vehicles, and xijk is the binary variable indicating that vehicle k travels from i to j.

Here is our working model file so far:

param N >= 0; 

param k >= 0; 

set dem_Nodes := {2..N}; 

set Nodes ordered := {1..N}; 

set veh := {1..k}; 

set Arcs := {i in Nodes, j in Nodes: i<>j}; 

param Q{veh}>0; 

param q{Nodes}>=0; 

param D{Arcs}; 

var x{Arcs, veh}, binary; 

var y{Arcs}, binary; 

        minimize Total_dist: 

                sum {t in veh} sum {(i,j) in Arcs} D[i,j] * x[i,j,t]; 

        subject to Start{j in dem_Nodes}: 

                sum{i in Nodes: i<>j} y[i,j]=1; 

        subject to Continue{i in dem_Nodes}: 

                sum{(i,j) in Arcs: i<>j} y[i,j]=1; 

        subject to Going: 

                sum{j in dem_Nodes, i in Nodes: i<>j} y[1,j]=k; 

        subject to Returning: 

                sum{i in dem_Nodes, j in Nodes: i<>j} y[i,1]=k; 

 

        subject to Capacity: 

               sum {t in veh} sum {i in dem_Nodes, j in Nodes: i<>j} x[i,j,t]*q[j]<=Q[k]; 

        subject to Link: 

               sum {t in veh} sum{i in Nodes, j in Nodes: i<>j} x[i,j,t] = sum{i in Nodes, j in Nodes: i<>j} y[i,j];

Any help in how to include time window constraints would be greatly appreciated!

Thank you,

Kevin

[kevin.r...@gmail.com]

I've come up with a potential solution to this problem, but I'm getting a syntax error:

line 8 (offset 190):

 syntax error

context: set start_time := (i in Nodes, k >>> in <<< veh);

Here is the updated model file:

param N >= 0; 

param k := 3; 

set dem_Nodes := {2..N}; 

set Nodes ordered := {1..N}; 

set veh := {1..k}; 

set Arcs := {i in Nodes, j in Nodes: i<>j};

set start_time := {i in Nodes, k in veh};

set end_time := {j in Nodes, k in veh};

param Q{veh}>0; 

param q{Nodes}>=0; 

param D{Arcs}; 

param s{starttime};

param e{endtime};

param a{Nodes}>=0;

param b{Nodes}>=0;

var x{Arcs, veh}, binary; 

var y{Arcs}, binary; 

minimize Total_dist: 

sum {t in veh} sum {(i,j) in Arcs} D[i,j] * x[i,j,t]; 

subject to Start{j in dem_Nodes}: 

sum{i in Nodes: i<>j} y[i,j]=1; 

subject to Continue{i in dem_Nodes}: 

sum{(i,j) in Arcs: i<>j} y[i,j]=1; 

subject to Going: 

sum{j in dem_Nodes, i in Nodes: i<>j} y[1,j]=k; 

subject to Returning: 

sum{i in dem_Nodes, j in Nodes: i<>j} y[i,1]=k; 

subject to Capacity: 

sum {t in veh} sum {i in dem_Nodes, j in Nodes: i<>j} x[i,j,t]*q[j]<=Q[k]; 

subject to Servedonly: 

sum {t in veh} sum{i in Nodes, j in Nodes: i<>j} x[i,j,t] = sum{i in Nodes, j in Nodes: i<>j} y[i,j];

subject to Timewindow {i in Nodes, j in Nodes, k in veh}:

start_time[i,k] + D[i,j] - 3*(1 - x[i,j,k])<=endtime[j,k];

subject to StartTime {i in Nodes, k in veh}:

start_time[i,k] >= a[i]

subject to EndTime {i in Nodes, k in veh}:

start_time[i,k] <= b[i]

Perhaps my start_time and end_time sets cannot be indexed on {i in Nodes, k in veh} and {j in Nodes, k in veh} respectively? And if this is the case, how could I have a set that has values based on, for example, node i and vehicle k?

Thanks again, any help would be greatly appreciated!

Kevin

[Robert Fourer]

You have already defined

param k := 3;

so then you get a syntax error when attempting to use k as a dummy index as in

set start_time := {i in Nodes, k in veh};

Either of the following would work here:

set start_time := {i in Nodes, v in veh};
set start_time := {Nodes, veh};

You don't really need the dummy indices in this statement since they aren't used for any purpose in the definition of set start_time.

Bob Fourer
am...@googlegroups.com

=======

From: am...@googlegroups.com [mailto:am...@googlegroups.com] On Behalf Of kevin.r...@gmail.com
Sent: Tuesday, December 16, 2014 9:33 AM
To: am...@googlegroups.com
Cc: kevin.r...@gmail.com
Subject: [AMPL 9771] Re: Vehicle Routing Problem - How to Account for Time Windows?

I've come up with a potential solution to this problem, but I'm getting a syntax error:

line 8 (offset 190):
syntax error
context: set start_time := (i in Nodes, k >>> in <<< veh);

Here is the updated model file:

param N >= 0;
param k := 3;

set dem_Nodes := {2..N};
set Nodes ordered := {1..N};
set veh := {1..k};
set Arcs := {i in Nodes, j in Nodes: i<>j};
set start_time := {i in Nodes, k in veh};
set end_time := {j in Nodes, k in veh};

...

[Prabhupad Bharadwaj]

can you show the formulation so that it will be helpful for me

[nourhan...@gmail.com]

can you provide me with the mathematical model because I'm working now on coding the VRPTW on Ampl , this will help me a lot.

[otav...@gmail.com]

How can I model my "Printf" and my "data" to this case? I will try to study it in Gusek.

Thanks

[AMPL Google Group]

Are you asking if there is any printf statement in AMPL? You can read about AMPL print, printf commands at https://ampl.com/BOOK/CHAPTERS/15-display.pdf. If this doesn't answer your question, please clarify your question.

Thanks,

--
Paras Tiwari
am...@googlegroups.com

{#HS:566115175-5827#}

--
You received this message because you are subscribed to the Google Groups "AMPL Modeling Language" group.
To unsubscribe from this group and stop receiving emails from it, send an email to ampl+uns...@googlegroups.com.
To post to this group, send email to am...@googlegroups.com.
Visit this group at https://groups.google.com/group/ampl.
For more options, visit https://groups.google.com/d/optout.

[Otavio Rezende]

I need to study VRPWT cases. I thoght if I could take a code and solve some possible cases like in Ulysses 16, where I have the code and the data to run the code. I use Gusek tu run it.

So I asked about the code in discussion here (https://groups.google.com/forum/#!topic/ampl/Vi7RYuNfS0M) or if you have some examples of VRP and VRPWT with data that I can run it on Gusek to study it.

Otávio Sousa Rezende

Graduando em Engenharia Civil - UNIFEI

To unsubscribe from this group and stop receiving emails from it, send an email to ampl+unsubscribe@googlegroups.com.

To post to this group, send email to am...@googlegroups.com.
Visit this group at https://groups.google.com/group/ampl.
For more options, visit https://groups.google.com/d/optout.

--
You received this message because you are subscribed to a topic in the Google Groups "AMPL Modeling Language" group.
To unsubscribe from this topic, visit https://groups.google.com/d/topic/ampl/Vi7RYuNfS0M/unsubscribe.
To unsubscribe from this group and all its topics, send an email to ampl+unsubscribe@googlegroups.com.

[AMPL Google Group]

Sorry, we don't have access to VRTP model. However, there are several other examples similar to VRTP. You can find the model/ directory inside your ampl/ directory and check several different models in AMPL. Moreover, https://ampl.com/BOOK/CHAPTERS/18-network.pdf will be a helpful chapter to review.

--
Paras Tiwari
am...@googlegroups.com

{#HS:566115175-5827#}

On Mon, Apr 23, 2018 at 7:16 PM UTC, Ampl Modeling Language <am...@googlegroups.com> wrote:

I need to study VRPWT cases. I thoght if I could take a code and solve some possible cases like in Ulysses 16, where I have the code and the data to run the code. I use Gusek tu run it.
So I asked about the code in discussion here (https://groups.google.com/forum/#!topic/ampl/Vi7RYuNfS0M) or if you have some examples of VRP and VRPWT with data that I can run it on Gusek to study it.



Otávio Sousa Rezende
Graduando em Engenharia Civil - UNIFEI

On Mon, Apr 23, 2018 at 3:48 PM UTC, AMPL Google Group <am...@googlegroups.com> wrote:

Are you asking if there is any printf statement in AMPL? You can read about AMPL print, printf commands at https://ampl.com/BOOK/CHAPTERS/15-display.pdf. If this doesn't answer your question, please clarify your question.

Thanks,

--
Paras Tiwari
am...@googlegroups.com

To unsubscribe from this group and stop receiving emails from it, send an email to ampl+uns...@googlegroups.com.

[Otavio Rezende]

Hey,

I would like a code to model Salomon's cases.

I can find the data, but not the codes.

If you could help me. 

Thanks.

Otávio Sousa Rezende

Graduando em Engenharia Civil - UNIFEI

To unsubscribe from this group and stop receiving emails from it, send an email to ampl+unsubscribe@googlegroups.com.

To post to this group, send email to am...@googlegroups.com.
Visit this group at https://groups.google.com/group/ampl.
For more options, visit https://groups.google.com/d/optout.

--

You received this message because you are subscribed to a topic in the Google Groups "AMPL Modeling Language" group.
To unsubscribe from this topic, visit https://groups.google.com/d/topic/ampl/Vi7RYuNfS0M/unsubscribe.
To unsubscribe from this group and all its topics, send an email to ampl+unsubscribe@googlegroups.com.

[AMPL Google Group]

It's necessary for you to come up with the mathematical model and implement it into AMPL. If you face any issue while building the models, you could post your questions in the forum and we will help you to solve your issues.

Thanks,
Paras

--
Paras Tiwari
am...@googlegroups.com

{#HS:566115175-5827#}

On Thu, May 17, 2018 at 7:10 PM UTC, Ampl Modeling Language <am...@googlegroups.com> wrote:

Hey,

I would like a code to model Salomon's cases.
I can find the data, but not the codes.

If you could help me.

Thanks.



Otávio Sousa Rezende
Graduando em Engenharia Civil - UNIFEI

On Mon, Apr 23, 2018 at 10:29 PM UTC, AMPL Google Group <am...@googlegroups.com> wrote:

Sorry, we don't have access to VRTP model. However, there are several other examples similar to VRTP. You can find the model/ directory inside your ampl/ directory and check several different models in AMPL. Moreover, https://ampl.com/BOOK/CHAPTERS/18-network.pdf will be a helpful chapter to review.

--
Paras Tiwari
am...@googlegroups.com

To unsubscribe from this group and stop receiving emails from it, send an email to ampl+uns...@googlegroups.com.