# Late and Early Costs per minute for a delivery problem

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!

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.

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.