Late and Early Costs per minute for a delivery problem

Question

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!

Answer 1

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.

Answer 2

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.