In many OR problems, it is sometimes a good idea (or necessary) to relax routing constraints.

An example of this occurs in the classical facility location problem, where a warehouse can send out a truck that makes several stops at different stores on the same route. In this case, transportation costs are no longer a simple point-to-point rate, they depend on which stores are on which route, and it is difficult to allocate the costs of the routes to each individual stop. Of course one could model the routing part of the problem, but besides the size issue, there many be differing levels of detail in the routing versus network design problems, and it may be counter productive to combine the two in a unique model.

A good compromise is to relax the routing constraints, but to estimate the multistop routing costs. In this book, the authors propose the following methodology. Suppose you are dealing with one warehouse and $3$ stores.

  1. Compute the costs out and back from the warehouse to each the stores, assuming a full truckload.
  2. Add the $3$ costs together. Let $c_1$ denote this cost.
  3. Since multistop routes are typically ran for more frequent deliveries, it is reasonnable to assume that each route delivers only a fraction of the store's demand, e.g. one third. So a fair comparison between the direct full truckload route and the multistop route, is to run the multistop route $3$ times, which yields a second cost $c_2$.
  4. Between the warehouse and each store, multiply each point-to-point cost by $\frac{c_2}{c_1}$. Note that if the stores are all very far away from the warehouse, and close to one another, this factor will be very close to $1$.

This methodology has some strengths, but one major downside is that you have to compute $c_2$ in the first place, that is, you have to compute a potentially hard route before hand. A way around this is to simply multiply each cost by $1+\varepsilon$, where $\varepsilon$ is estimated somehow, but this obviously lacks accuracy.

Another example is described in this paper, in which the authors formulate their inventory routing problem as a MILP, and then introduce a relaxation without routing model which eliminates the routing part of the problem. They basically introduce fractional vehicles and underestimate the costs by considering the distance to and from the depot only.

Last but not least, I have seen the following method in the past. The cost is estimated as follows: two terms are considered, the direct point-to-point distance, and an estimation of the average distance between stops, multiplied by an estimation of the average number of stops per route. This average distance $\bar{d}$ is computed with the following formula : $$ \bar{d} \approx \frac{2}{\sqrt{\mbox{node density} \times \pi}} $$

My questions:

  1. Are there other ways to model/estimate routing costs in such problems, without explicitely computing the routes ?
  2. Does anyone have a reference detailing the last methodology that is described above (with $\bar{d}$).
  • $\begingroup$ I vaguely remember a paper by Turkensteen and Klose from 2012, where I think they make some estimates in that nature. I haven't reread the paper, so it might be a dead end (sorry in advance). You can find the paper here sciencedirect.com/science/article/pii/… $\endgroup$
    – Sune
    Nov 4 '20 at 16:38
  • $\begingroup$ Interesting paper, thanks! $\endgroup$
    – Kuifje
    Nov 4 '20 at 17:11

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.