Vehicle Routing Problem with Time Window Penalty

[Kevin Grahadian]

Hello there, 

I am working on VRPTW model right now and I have a problem regarding the time penalty in it. In the code below where I bold it, I want to save the total time by vehicle K reach in each nodes. But I just realize that if I want to use 'if' in AMPL, it cannot accept variables for the condition because I keep getting error message like "variable in = expression".

Do you have any solution for the problem to save the total time in each nodes so I can refer to some numbers like the formula below? Also I provide you with the mathematical model in the journal below. 

I do have one more problem to account the time window. Do you guys any idea how to create the constraint of time window? I have idea about it that I should save the time in each node where the truck go, but I don't know how to save it in AMPL.

Of maybe some of you have worked how to create VRPTW in AMPL could provide the source code? Thank you so much in advance.

--------------------------------------------------------------------------------

param N >= 0; #Number of nodes
param Vehicle >= 0; #Number of available Vehicles

set V := 0..N;
set NODES := {i in V, j in V: i <> j};
set V2:= 1..N;
set M := 1..Vehicle;

#Parameter
param cost {NODES}; #Cost from Nodes i to j
param demand {V2}; #demand for each nodes (Customer)
param capacity{M}; #Capacity of vehicles k
param UB {V2}; #Upper bound (time)
param LB {V2}; #Lower Bound (time)

#Decision Variable
var xijk {i in V, j in V, k in M: i<>j} >= 0 binary; #Decision variable, 1 if k vehichle go from node i to j
var yik {i in V, k in M} binary; #Decision variable, 1 if k vehichle serve customer k
var u {i in V, k in M} >= 0; #Route (Sub tour elimination)
var Total_Time{i in V2, k in M}>=0; #Total Waktu yang dibutuhkan

#Penalty parameter
param alpha>=0; #Penalty if Tj<LB
param beta>=0; #Penalty if Tj>UB
param Penalty {i in V2, k in M} =     if Total_Time[i,k] > UB[i] then alpha
                                     else if Total_Time[i,k] < LB[i] then beta
                                    else 0;

#Objective Function
minimize Total_Cost:
    sum {i in V, j in V, k in M: i<>j} cost[i,j]*xijk[i,j,k];

#Constraint
#VRP Constraint
subject to Enter {j in V2, k in M}: sum{i in V:i<>j}xijk[i,j,k]-yik[j,k]==0;
subject to Leave {i in V2, k in M}:    sum{j in V:i<>j}xijk[i,j,k]-yik[i,k]==0;
subject to StartEnd {k in M}:        sum{j in V2}xijk[0,j,k]-yik[0,k]==0; #Dimulai dan diakhiri di depot yang sama
subject to VehCap {k in M}:         sum{i in V2} demand[i]*yik[i,k]<=capacity[k]*yik[0,k]; #Tidak melebihi kapasitas kendaraan
subject to CustServed {i in V2}:    sum{k in M}yik[i,k]==1; #Setiap Customer dilayani oleh sebuah kendaraan
#SubTourConstraint
subject to SubTour1 {k in M}:        u[0,k]==1;
subject to SubTour2 {i in V2, k in M}: u[i,k]<=N;
subject to SubTour3 {i in V2, k in M}: u[i,k]>=2;
subject to SubTour4 {i in V, j in V2, k in M: i <> j}: u[i,k]-u[j,k]+1<=(N-1)*(1-xijk[i,j,k]);

[AMPL Google Group]

The immediate problem here is that you cannot define a param (Penalty) by an expression that uses a var (Total_Time). In this situation, Penalty also has to be a var.

The paper's expression for the penalty in (1) and (2) is written in a very awkward way, but I think it is just a sum of 3-piece piecewise-linear functions. See chapter 17. Piecewise-Linear Programs for an explanation of how to write piecewise-linear functions in AMPL.

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

{#HS:1926879333-110638#}