4
$\begingroup$

I'm currently struggling with a MIP. Have to model a truck delivering packages for customers in the set $C = \{1,2,3,4,5\}$. The travel time from location $i$ to $j$ I've defined as $t_{ij}$. The truck must start from location 0 and can travel to any customer in any order, provided all customers are visited. I've set the variable $x_{ij}$ to be 1 if the truck travel from location $i$ to $j$ and 0 otherwise.

I'm struggling with this part of the problem. Each customer has a time $E_i$ as the earliest allowed time of arrival for customer $i$ and $L_i$ as the latest possible time of arrival. If the truck arrives early it's charged 3 dollars /min early and 2 dollars/min late.

I've had trouble adding that into my objective function and as a constraint. So far I've attempted to use the variable $A_i$ to represent time of arrival to location $i$. Unfortunately the issue here is I am unable to find a way to determine the order of the deliveries to sum the time.

Any insight would be much appreciated, thank you!

$\endgroup$
1

2 Answers 2

3
$\begingroup$

The constraints you need to set the value of variables $A_i$ correctly are a generalisation of the famous Miller-Tucker-Zemlin (MTZ) constraints.

For example, you can use $A_j \geq A_i + t_{ij} - M(1 - x_{ij})$, for a sufficiently large constant $M$. You have one constraint for each arc $(i,j)$ and $j \neq 0$. Now you must compute eventual early and late arrivals.

Introduce two variables for each customer. Variable $\epsilon_i \geq 0$ will tell you how early you arrived at $i$ if you arrived early; otherwise, it will be 0. Variable $\lambda_i \geq 0$ will tell you how late you arrived at $i$ if you arrived late; otherwise, it will be 0.

In other words, you would like these variables to hold values

$$\epsilon_i = \max \{ E_i - A_i, 0 \}\mathrm{,}\quad \lambda_i = \max \{ A_i - L_i, 0 \}\mathrm{.}$$

The problem is that the $\max$ function is not linear, so you must devise a linear constraint to set the values of $\epsilon_i$ and $\lambda_i$. Because both $\epsilon_i$ and $\lambda_i$ are non-negative by definition and because they are penalised in the objective function, you can use

$$\epsilon_i \geq E_i - A_i\mathrm{,}\quad \lambda_i \geq A_i - L_i\mathrm{.}$$

The following figures show the difference that adding the penalties makes. The first figure shows the optimal solution without early/late penalties; the second figure is with the penalties. The blue point is the depot, and the orange points are the customers. Values above the customers are the $[E_i, L_i]$ time windows; values below the customers are arrival times (in red if early or late). Values on the edges are traversing times.

Solution without penalties. Solution with penalties.

$\endgroup$
1
$\begingroup$

The problem you are describing is a version of what is known as a Vehicle Routing Problem with Time Windows (VRPTW). If you enter VRPTW in the search box for this site, you'll find a gaggle of problems about them, and of course you could google the phrase (or acronym). Among the hits you are likely to find some model formulations.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.