Electric Vehicle Routing Problem with Time Windows (EVRPTW)

[Mertcan Daysalılar]

Hello,

I am currently working on the EVRPTW for heterogeneous fleet. However, I am struggling to code sets in AMPL( Especially, I do not know how to create dummy set). Could someone please help me in that regards? I attached the sets, variables and parameters below. I hope somebody can help me. Thank you.

Best regards,

Mertcan

[AMPL Google Group]

When someone is writing mathematical notation, they are not prevented from being unclear or imprecise -- and that seems to be part of the problem here. Defining the customer/depot V-sets in AMPL does look straightforward:

param N integer > 0;
set V = 1..N;
set V0 = {0} union V;
set VNplus1 = V union {N+1};

However, it is not clear what the members of the F-sets (F and F') are supposed to look like. There are several sets that contain both customers and charging stations, so apparently they are to be computed as the union of V-sets and F-sets; but that only tells us that the F-sets cannot contain the numbers 0 through N+1. But if you can figure out what the members of the F-sets should be, then you can write definitions in AMPL like this:

set F;
set Fprime;
set V0prime = V0 union F union Fprime;

Unfortunately, the definition of sets like V0prime depends on a set called V', and no formula for V' is given in the mathematical statement. Thus you will have to use your knowledge of the problem to figure out what is really the right AMPL formula for sets like V0prime.

--
Robert Fourer
am...@googlegroups.com

{#HS:2008874972-111911#}

[Mertcan Daysalılar]

Dear Fourer,

Thank you for your reply. Actually, Vprime was equal to V union Fprime. 

The thing that I cannot understand fully is related to F and Fprime sets. Fprime set of recharging stations with their copies. Since the recharging station may be visited multiple times by the same vehicle or different vehicles I create sufficient number of copies and allow at most one visit to each in the mathematical model. If we define F and Fprime sets like you indicated above, how can I enter data in the data file? 

In addition, when creating V0 and VNplus1, how does the ampl read {0} and {N+1}? Does it read as a string or integer? 

Best regards,

Mertcan 

[AMPL Google Group]

As an example, if there are two charging stations and you want three copies of each, you could write the data as

set F := A B ;
set Fprime := A1 A2 A3 B1 B2 B3 ;

But it may be more convenient to compute Fprime from F, by defining

param nCopies integer > 0;
set F;
set Fprime = setof {f in F, i in 1..nCopies} f & i;

Here & is the string concatenation operator, so after reading this data,

param nCopies := 3 ;
set F := A B ;

you get

ampl: display F, Fprime;
set F := A B;
set Fprime := A1 A2 A3 B1 B2 B3;

To answer your other question, {0} and {N+1} are read as sets of numbers. Thus V, V0, and VNplus1 will all be sets of numbers. But with F and Fprime defined as above, V union Fprime will have some numbers and some strings as members. You can use a set like that, if it makes sense for your model.

--
Robert Fourer
am...@googlegroups.com

{#HS:2008874972-111911#}

On Thu, Sep 15, 2022 at 6:30 PM UTC, AMPL Google Group <am...@googlegroups.com> wrote:

When someone is writing mathematical notation, they are not prevented from being unclear or imprecise -- and that seems to be part of the problem here. Defining the customer/depot V-sets in AMPL does look straightforward:

param N integer > 0;
set V = 1..N;
set V0 = {0} union V;
set VNplus1 = V union {N+1};

However, it is not clear what the members of the F-sets (F and F') are supposed to look like. There are several sets that contain both customers and charging stations, so apparently they are to be computed as the union of V-sets and F-sets; but that only tells us that the F-sets cannot contain the numbers 0 through N+1. But if you can figure out what the members of the F-sets should be, then you can write definitions in AMPL like this:

set F;
set Fprime;
set V0prime = V0 union F union Fprime;

Unfortunately, the definition of sets like V0prime depends on a set called V', and no formula for V' is given in the mathematical statement. Thus you will have to use your knowledge of the problem to figure out what is really the right AMPL formula for sets like V0prime.

--
Robert Fourer
am...@googlegroups.com

[Mertcan Daysalılar]

Dear Fourer,

Thank you so much for explaining. It is more clear now.Basically, depot nodes {0} and {N+1} are at the same location. Each vehicle must begin to trip at the {0} depot and end in depot{N+1}. Customers,depot and charging stations have (x,y) coordinates. I am trying to define a data file but I am a little bit fuzzy about how to do that, For instance, the model has dij{i in V0prime,j in VNplus1prime:i<>j}. Distance will be calculated by using the Euclidean distance formula(sqrt(((ax[i]-bx[i])^2+(ay[i]-by[i])^2))). How can I put the locations in a data file and calculate the distance between two locations? Could you help me in this regard? Thank you.

Best regards,

Mertcan

--
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/ZEa9iyswZNE/unsubscribe.
To unsubscribe from this group and all its topics, send an email to ampl+uns...@googlegroups.com.
To view this discussion on the web visit https://groups.google.com/d/msgid/ampl/reply-77152-2008874972-5982691895-1663645287-230552940%40helpscout.net.

[AMPL Google Group]

The mathematical model description suggests that the distances d are part of the data, but I guess you want to supply coordinates instead as part of the data, and then compute the distances. So you could have:

set V0Nplus1prime = Vprime union {0} union {N+1};
param xcoord {V0Nplus1prime};
param ycoord {V0Nplus1prime};
param d {i in V0prime, j in VNplus1prime: i<>j} =
   sqrt((xcoord[i]-xcoord[j])^2 + (ycoord[i]-ycoord[j])^2);

Then in the data file, you just need to give xcoord and ycoord values corresponding to every member of V0Nplus1prime. You can put them in one table in the AMPL data file; for an example of giving data for two params in one table, see Figure 2-2 of the AMPL book.

--
Robert Fourer
am...@googlegroups.com

{#HS:2008874972-111911#}

On Tue, Sep 20, 2022 at 1:04 PM UTC, AMPL Modeling Language <am...@googlegroups.com> wrote:

Dear Fourer,

Thank you so much for explaining. It is more clear now.Basically, depot nodes {0} and {N+1} are at the same location. Each vehicle must begin to trip at the {0} depot and end in depot{N+1}. Customers,depot and charging stations have (x,y) coordinates. I am trying to define a data file but I am a little bit fuzzy about how to do that, For instance, the model has dij{i in V0prime,j in VNplus1prime:i<>j}. Distance will be calculated by using the Euclidean distance formula(sqrt(((ax-bx)^2+(ay-by)^2))). How can I put the locations in a data file and calculate the distance between two locations? Could you help me in this regard? Thank you.

Best regards,
Mertcan

On Tue, Sep 20, 2022 at 3:41 AM UTC, AMPL Google Group <am...@googlegroups.com> wrote:

As an example, if there are two charging stations and you want three copies of each, you could write the data as

set F := A B ;
set Fprime := A1 A2 A3 B1 B2 B3 ;

But it may be more convenient to compute Fprime from F, by defining

param nCopies integer > 0;
set F;
set Fprime = setof {f in F, i in 1..nCopies} f & i;

Here & is the string concatenation operator, so after reading this data,

param nCopies := 3 ;
set F := A B ;

you get

ampl: display F, Fprime;
set F := A B;
set Fprime := A1 A2 A3 B1 B2 B3;

To answer your other question, {0} and {N+1} are read as sets of numbers. Thus V, V0, and VNplus1 will all be sets of numbers. But with F and Fprime defined as above, V union Fprime will have some numbers and some strings as members. You can use a set like that, if it makes sense for your model.

--
Robert Fourer
am...@googlegroups.com

[Mertcan Daysalılar]

Hello,

I implemented what you explained to my model and data file. However, I am getting error like below although i put the value for 71,72,81, and 82.(These are my dummy charging stations' location)  How can I solve this problem?

error executing "display" command:

error processing param xcoord:

4 invalid subscripts discarded:

xcoord[71]

xcoord[72]

xcoord[81]

and 1 more.

Error executing "display" command:

error processing param ycoord:

4 invalid subscripts discarded:

ycoord[71]

ycoord[72]

ycoord[81]

and 1 more.

Error executing "display" command:

error processing param dij[0,'71']:

no value for xcoord['71']

--
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/ZEa9iyswZNE/unsubscribe.
To unsubscribe from this group and all its topics, send an email to ampl+uns...@googlegroups.com.

To view this discussion on the web visit https://groups.google.com/d/msgid/ampl/reply-77152-2008874972-5986288208-1663727367-1028596940%40helpscout.net.

[AMPL Google Group]

You're right that you are getting this error because the index set for xcoord and ycoord does not contain 71, 72, 81, and 82. So you need to look at the index sets in your "param xcoord" and "param ycoord" statements, and ask yourself why those sets do not contain the four dummy charging station values.

To troubleshoot this problem, you can use AMPL's display command to see which sets contain 71, 72, 81, and 82, and which do not. For example, "display V0Nplus1prime;" will show all the members of set V0Nplus1prime.

--
Robert Fourer
am...@googlegroups.com

{#HS:2008874972-111911#}

On Tue, Sep 27, 2022 at 2:43 PM UTC, AMPL Modeling Language <am...@googlegroups.com> wrote:

Hello,

I implemented what you explained to my model and data file. However, I am getting error like below although i put the value for 71,72,81, and 82.(These are my dummy charging stations' location) How can I solve this problem?

error executing "display" command:
error processing param xcoord:

4 invalid subscripts discarded:
xcoord[71]
xcoord[72]
xcoord[81]
and 1 more.

Error executing "display" command:
error processing param ycoord:

4 invalid subscripts discarded:
ycoord[71]
ycoord[72]
ycoord[81]
and 1 more.

Error executing "display" command:
error processing param dij[0,'71']:
no value for xcoord['71']

On Wed, Sep 21, 2022 at 2:29 AM UTC, AMPL Google Group <am...@googlegroups.com> wrote:

The mathematical model description suggests that the distances d are part of the data, but I guess you want to supply coordinates instead as part of the data, and then compute the distances. So you could have:

set V0Nplus1prime = Vprime union {0} union {N+1};
param xcoord {V0Nplus1prime};
param ycoord {V0Nplus1prime};
param d {i in V0prime, j in VNplus1prime: i<>j} =
   sqrt((xcoord[i]-xcoord[j])^2 + (ycoord[i]-ycoord[j])^2);

Then in the data file, you just need to give xcoord and ycoord values corresponding to every member of V0Nplus1prime. You can put them in one table in the AMPL data file; for an example of giving data for two params in one table, see Figure 2-2 of the AMPL book.

--
Robert Fourer
am...@googlegroups.com

[Mertcan Daysalılar]

Hello, 

I have been working on EVRP and trying to code mathematical models in AMPL. After I was done with the model, I tried to check my model with a toy problem. However, I am getting an error message like below.

20.1.0.0: integer infeasible.

0 MIP simplex iterations

0 branch-and-bound nodes

No basis.

Could you please check my model and let me know what I am missing?

Thank you.

Best regards,

Mertcan

--
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/ZEa9iyswZNE/unsubscribe.
To unsubscribe from this group and all its topics, send an email to ampl+uns...@googlegroups.com.

To view this discussion on the web visit https://groups.google.com/d/msgid/ampl/reply-77152-2008874972-6006113580-1664310084-1208693663%40helpscout.net.

[AMPL Google Group]

An "integer infeasible" message from the solver means that there is no way to assign values to the variables that are within the variables' bounds and that also satisfy all of the constraints -- and that also satisfy the "integer" or "binary" requirements on the variables. This may be due to an error in your model. Or it may be that your data simply doesn't permit a feasible solution; for example, some capacities like Q or C might be too low to allow all services to be made.

There is no simple and general way to deal with an error like this; you may need to study the paper and the model for a while before you can understand the cause of the infeasibility. It is possible to suggest some good ways to get started, however.

As an initial troubleshooting step, it is often helpful to use AMPL's expand command to see whether AMPL generated the constraints that you expected. By itself, expand; shows all of the constraints. If there are many of them, you can use, for example, expand C1; to expand all of the constraints that have a particular name. Also you can write, for instance, expand >listing.txt; or expand C1 >listing.txt; to send all of the output to the file listing.txt.

You should also consider using AMPL's drop and restore commands to narrow your search for the cause of the infeasibility. If you drop some constraints and the resulting problem is still infeasible, then you don't need to consider the dropped constraints in looking for the cause of infeasibility. By trying a series of drops, you may be able to determine that infeasibility is being caused by only a small subset of the constraints.

If you are using one of the popular MIP solvers (CPLEX, Gurobi, Xpress) then to get more help with diagnosing the infeasibility, you can ask the solver to compute an irreducible infeasible subset. For more on this topic, take a look at the explanation of the "iisfind" option in https://secure.helpscout.net/conversation/1190184366/79732/, and also see the discussion of "infeasibility diagnosis" in chapter 14 of the AMPL book (https://ampl.com/BOOK/CHAPTERS/17-solvers.pdf#page=25).

--
Robert Fourer
am...@googlegroups.com

{#HS:2008874972-111911#}

On Mon, Dec 12, 2022 at 10:44 PM UTC, AMPL Modeling Language <am...@googlegroups.com> wrote:

Hello,

I have been working on EVRP and trying to code mathematical models in AMPL. After I was done with the model, I tried to check my model with a toy problem. However, I am getting an error message like below.

20.1.0.0: integer infeasible.
0 MIP simplex iterations
0 branch-and-bound nodes
No basis.

Could you please check my model and let me know what I am missing?

Thank you.

Best regards,
Mertcan

On Tue, Sep 27, 2022 at 8:21 PM UTC, AMPL Google Group <am...@googlegroups.com> wrote:

You're right that you are getting this error because the index set for xcoord and ycoord does not contain 71, 72, 81, and 82. So you need to look at the index sets in your "param xcoord" and "param ycoord" statements, and ask yourself why those sets do not contain the four dummy charging station values.

To troubleshoot this problem, you can use AMPL's display command to see which sets contain 71, 72, 81, and 82, and which do not. For example, "display V0Nplus1prime;" will show all the members of set V0Nplus1prime.

--
Robert Fourer
am...@googlegroups.com

[Mertcan Daysalılar]

Hi Robert,

Thank you so much for quick response. I will try what you suggested. 

Best,

Mertcan

--
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/ZEa9iyswZNE/unsubscribe.
To unsubscribe from this group and all its topics, send an email to ampl+uns...@googlegroups.com.

To view this discussion on the web visit https://groups.google.com/d/msgid/ampl/reply-77152-2008874972-6234723685-1670947968-2066296037%40helpscout.net.

[Mertcan Daysalılar]

Dear Fourer,

I hope you are doing well.

I have a question about the F and Fprime. After creating copies of set F, we'll get the same values for each copy. I want to put the values only for set F and make the AMPL read the same value for each copy. Can we do that?  I tried to give an example of my question briefly,

Let us say we have 5 customers and 2 charging stations. The model has 3 copies of each charging station (CS). As you explained in the previous email; 

set F := 7 8 9;
set Fprime := '71' '72' '73'  '81' '82' '83' '91' '92' '93' ;

param nCopies integer > 0;
set F;
set Fprime = setof {f in F, i in 1..nCopies} f & i;

param nCopies := 3 ;
set F := 7 8 9 ;

While creating the data file, I wrote all CS's copies' locations one by one, like below.  It does not seem the proper way to me. For larger data sizes, it increased the computation time. Could you please let me know if there is a way?

param: xcoord ycoord:= #location of each point

0   40.0       50.0

1   8.0        40.0

2   40.0       15.0          

3   30.0       60.0       

4   27.0       43.0          

5   65.0       85.0                          

6   40.0       50.0             

'71'  57.0     82.0  

'72'  57.0     82.0

'73'  14.0     82.0    

'81'  14.0     59.0 

'82'  14.0     59.0    

'83'  14.0     59.0

'91'  39.0     26.0

'92'  39.0     26.0

'93'  39.0     26.0

; 

Thank you so much in advance.

Best regards,

Mertcan

--
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/ZEa9iyswZNE/unsubscribe.
To unsubscribe from this group and all its topics, send an email to ampl+uns...@googlegroups.com.

To view this discussion on the web visit https://groups.google.com/d/msgid/ampl/reply-77152-2008874972-5982691895-1663645287-230552940%40helpscout.net.

[AMPL Google Group]

It can be done, but it depends somewhat on how you are defining xcoord and ycoord and maybe other model components. Can you attach the full model and data files again? (I have the old ones, but they probably have changed.)

--
Robert Fourer
AMPL Forum

{#HS:2008874972-111911#}

On Thu, Feb 16, 2023 at 1:42 PM UTC, AMPL Modeling Language <am...@googlegroups.com> wrote:

Dear Fourer,

On Tue, Dec 13, 2022 at 6:01 PM UTC, AMPL Modeling Language <am...@googlegroups.com> wrote:

Hi Robert,

Thank you so much for quick response. I will try what you suggested.

Best,
Mertcan

On Tue, Dec 13, 2022 at 4:12 PM UTC, AMPL Google Group <am...@googlegroups.com> wrote:

An "integer infeasible" message from the solver means that there is no way to assign values to the variables that are within the variables' bounds and that also satisfy all of the constraints -- and that also satisfy the "integer" or "binary" requirements on the variables. This may be due to an error in your model. Or it may be that your data simply doesn't permit a feasible solution; for example, some capacities like Q or C might be too low to allow all services to be made.

There is no simple and general way to deal with an error like this; you may need to study the paper and the model for a while before you can understand the cause of the infeasibility. It is possible to suggest some good ways to get started, however.

As an initial troubleshooting step, it is often helpful to use AMPL's expand command to see whether AMPL generated the constraints that you expected. By itself, expand; shows all of the constraints. If there are many of them, you can use, for example, expand C1; to expand all of the constraints that have a particular name. Also you can write, for instance, expand >listing.txt; or expand C1 >listing.txt; to send all of the output to the file listing.txt.

You should also consider using AMPL's drop and restore commands to narrow your search for the cause of the infeasibility. If you drop some constraints and the resulting problem is still infeasible, then you don't need to consider the dropped constraints in looking for the cause of infeasibility. By trying a series of drops, you may be able to determine that infeasibility is being caused by only a small subset of the constraints.

If you are using one of the popular MIP solvers (CPLEX, Gurobi, Xpress) then to get more help with diagnosing the infeasibility, you can ask the solver to compute an irreducible infeasible subset. For more on this topic, take a look at the explanation of the "iisfind" option in https://secure.helpscout.net/conversation/1190184366/79732/, and also see the discussion of "infeasibility diagnosis" in chapter 14 of the AMPL book (https://ampl.com/BOOK/CHAPTERS/17-solvers.pdf#page=25).

--
Robert Fourer

AMPL Forum

On Mon, Dec 12, 2022 at 10:44 PM UTC, AMPL Modeling Language <am...@googlegroups.com> wrote:

Hello,

I have been working on EVRP and trying to code mathematical models in AMPL. After I was done with the model, I tried to check my model with a toy problem. However, I am getting an error message like below.

20.1.0.0: integer infeasible.
0 MIP simplex iterations
0 branch-and-bound nodes
No basis.

Could you please check my model and let me know what I am missing?

Thank you.

Best regards,
Mertcan

On Tue, Sep 27, 2022 at 8:21 PM UTC, AMPL Google Group <am...@googlegroups.com> wrote:

You're right that you are getting this error because the index set for xcoord and ycoord does not contain 71, 72, 81, and 82. So you need to look at the index sets in your "param xcoord" and "param ycoord" statements, and ask yourself why those sets do not contain the four dummy charging station values.

To troubleshoot this problem, you can use AMPL's display command to see which sets contain 71, 72, 81, and 82, and which do not. For example, "display V0Nplus1prime;" will show all the members of set V0Nplus1prime.

--
Robert Fourer

AMPL Forum

On Tue, Sep 27, 2022 at 2:43 PM UTC, AMPL Modeling Language <am...@googlegroups.com> wrote:

Hello,

AMPL Forum

On Tue, Sep 20, 2022 at 1:04 PM UTC, AMPL Modeling Language <am...@googlegroups.com> wrote:

Dear Fourer,

Thank you so much for explaining. It is more clear now.Basically, depot nodes {0} and {N+1} are at the same location. Each vehicle must begin to trip at the {0} depot and end in depot{N+1}. Customers,depot and charging stations have (x,y) coordinates. I am trying to define a data file but I am a little bit fuzzy about how to do that, For instance, the model has dij{i in V0prime,j in VNplus1prime:i<>j}. Distance will be calculated by using the Euclidean distance formula(sqrt(((ax-bx)^2+(ay-by)^2))). How can I put the locations in a data file and calculate the distance between two locations? Could you help me in this regard? Thank you.

Best regards,
Mertcan

On Tue, Sep 20, 2022 at 3:41 AM UTC, AMPL Google Group <am...@googlegroups.com> wrote:

As an example, if there are two charging stations and you want three copies of each, you could write the data as

set F := A B ;
set Fprime := A1 A2 A3 B1 B2 B3 ;

But it may be more convenient to compute Fprime from F, by defining

param nCopies integer > 0;
set F;
set Fprime = setof {f in F, i in 1..nCopies} f & i;

Here & is the string concatenation operator, so after reading this data,

param nCopies := 3 ;
set F := A B ;

you get

ampl: display F, Fprime;
set F := A B;
set Fprime := A1 A2 A3 B1 B2 B3;

To answer your other question, {0} and {N+1} are read as sets of numbers. Thus V, V0, and VNplus1 will all be sets of numbers. But with F and Fprime defined as above, V union Fprime will have some numbers and some strings as members. You can use a set like that, if it makes sense for your model.

--
Robert Fourer

AMPL Forum