[AMPL 9765] Vehicle Routing Problem - How to Account for Time Windows?

classic Classic list List threaded Threaded
5 messages Options
Reply | Threaded
Open this post in threaded view
|

[AMPL 9765] Vehicle Routing Problem - How to Account for Time Windows?

kevin.roman1992
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

--
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 [hidden email].
To post to this group, send email to [hidden email].
Visit this group at http://groups.google.com/group/ampl.
For more options, visit https://groups.google.com/d/optout.
Reply | Threaded
Open this post in threaded view
|

[AMPL 9771] Re: Vehicle Routing Problem - How to Account for Time Windows?

kevin.roman1992
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

--
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 [hidden email].
To post to this group, send email to [hidden email].
Visit this group at http://groups.google.com/group/ampl.
For more options, visit https://groups.google.com/d/optout.
Reply | Threaded
Open this post in threaded view
|

RE: [AMPL 9791] Re: Vehicle Routing Problem - How to Account for Time Windows?

Robert Fourer-2
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
[hidden email]

=======

From: [hidden email] [mailto:[hidden email]] On Behalf Of [hidden email]
Sent: Tuesday, December 16, 2014 9:33 AM
To: [hidden email]
Cc: [hidden email]
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};

...

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?


--
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 [hidden email].
To post to this group, send email to [hidden email].
Visit this group at http://groups.google.com/group/ampl.
For more options, visit https://groups.google.com/d/optout.
Reply | Threaded
Open this post in threaded view
|

[AMPL 14938] Re: Vehicle Routing Problem - How to Account for Time Windows?

Prabhupad Bharadwaj
In reply to this post by kevin.roman1992
can you show the formulation so that it will be helpful for me

On Tuesday, December 16, 2014 at 5:25:22 AM UTC+5:30, [hidden email] wrote:
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

--
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 [hidden email].
To post to this group, send email to [hidden email].
Visit this group at https://groups.google.com/group/ampl.
For more options, visit https://groups.google.com/d/optout.
Reply | Threaded
Open this post in threaded view
|

[AMPL 15292] Re: Vehicle Routing Problem - How to Account for Time Windows?

nourhanghanem93
In reply to this post by kevin.roman1992
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.


On Tuesday, December 16, 2014 at 1:55:22 AM UTC+2, [hidden email] wrote:
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

--
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 [hidden email].
To post to this group, send email to [hidden email].
Visit this group at https://groups.google.com/group/ampl.
For more options, visit https://groups.google.com/d/optout.