How to create an optimal pizza delivery plan and how to visualize it

Question

This question is quite open, and the actual problem comes from something you would probably consider an everyday niche (something you'd probably take for granted without really thinking about it). However:

I may not disclose the actual application's nature, but I found that pizza bakeries and pizza consumers make for a reasonable replacement. We have been asked to create an optimal pizza delivery plan. I guess we will also need an appropriate means of visualizing the plan when we want to communicate our results to the audience.

We have been given

• a list of pizza bakeries (roughly 50):

  • where each bakery is located
  • how efficient each bakery is at making pizza
  • each bakery's minimum and maximum load. A bakery may be shut down if the minimum load cannot be reached.

• a list of pizza consumers (a few thousand):

  • where each consumer is located
  • how many pizzas each consumer needs - it's a constant flow of pizza

• a network of roads with

  • start, intermediate, and end node
  • segment length (this might be different from the Euclidean distance between adjacent nodes)
  • road capacity (maximum number of pizzas on this segment)

Bakeries and consumers are located at road start or end nodes

Rules and metrics:

• pizza from multiple bakeries may be combined to serve a customer. This is encouraged if it helps
• multiple paths may lead from a bakery to a customer, and pizzas may be sent on different routes in multiple packages. This is also encouraged if it helps.
• for simplicity, let's assume that all pizzas are of the same quality.
• no other traffic other than pizza delivery is taking place.
• the effort for delivering a pizza increases linearly with distance.
• the effort for delivering a pizza increases with the square of road load.
• bakeries may be closed down as an initial condition, and stay closed.
• There's no limit to the number of customers per bakery (apart from the bakery's pizza capacity)

Bakery efficiency and delivery effort are two different numbers: there's probably a large number of feasible solutions with different overall bakery efficiency. It's possible to state maximum allowed delivery effort and minimum required efficiency, though.

So in short: what is a suitable approach to this problem in terms of optimization algorithms?

It's hard to visually compare delivery solutions just by showing the network with some numbers attached to it, so we're looking for a way of "telling the story". Chord diagrams or circular diagrams might be a possibility, but someone more experienced might have a better suggestion.

How can we visualize results? We'd like to show how more efficient bakeries are utilized (if they are) but also how the optimization has an impact on the delivery effort.

Answer 1

Problem Formulation

I can't guarantee that this is a perfect (or smallest-possible) formulation of the problem, but maybe it will help guide a better one.

The road network is a directed graph consisting of intersections (nodes) connected by roads (edges). As input information, assume that you have an adjacency matrix $\mathcal{A}$ enumerating the edges. $\mathcal{A}_{ij} = 1$ if road exists connecting traveling from $i$ to $j$, 0 otherwise. Also, for simplicity, assume that the producers/consumers live at intersections (roads can be split at actual locations to make this true, so no loss of generality here). It should be noted that $\mathcal{A}$ is likely to be extremely sparse (unless you work for Amazon and you're delivering things via drones...), so this should be exploited.

Let your decision variable, $X_{ijkl} \in \mathbb{R}_+$ represent the quantity of pizza being transported along road segment $ij$ (from $i$ to $j$) from producer $k$ to consumer $l$. Let $P_k \in\{0,1\}$ indicate whether producer $k$ is active. Let $Z_{kl}\in\{0,1\}$ represent whether producer $j$ is servicing consumer $k$. Let $Q_{kl}\in\mathbb{R}_+$ be the quantity of product sent from producer $k$ to consumer $l$. The other problem variables/parameters are as follows:

\begin{align} c_{ij} \in \mathbb{R}_+&= \text{Quadratic traffic cost coefficient of driving on road segment $ij$} \\ L_{ij} \in \mathbb{R}_+&= \text{Cost due to length of road segment $ij$} \\ e_k \in \mathbb{R}_+&= \text{Efficiency of producer $k$} \implies \frac{1}{e_k} \text{is cost of producer $k$}\\ C^{max}_k \in \mathbb{R}_+&= \text{Capacity of producer $k$} \\ C^{min}_k \in \mathbb{R}_+&= \text{Minimum load of producer $k$}\\ D_l \in \mathbb{R}_+&= \text{Demand of consumer $l$} \\ C^{road} &= \text{Road capacity, same sparsity as $\mathcal{A}$} \end{align}

Constraints \begin{align} X_{ijkl} &\le \mathcal{A}_{ij}C^{max}_k\quad\forall \; i,j,k,l \\ X_{ijkl} &\le Z_{kl}C^{max}_k \quad\forall \;i,j,k,l \\ \sum_{k} Q_{kl} &\ge D_l \quad \forall \; l\\ \sum_{l} Q_{kl} &\le C^{max}_k P_k \quad \forall \; k\\ \sum_{l} Q_{kl} &\ge C^{min}_k P_k \quad \forall \; k\\ Z_{kl} &\le P_k \quad \forall \; k,l \\ Q_{kl} &\le Z_{kl}C^{max}_k \quad \forall \; k,l\\ \sum_{k,l} X_{ijkl} &\le C^{road}_{ij} \quad \forall \; i,j \\ \sum_j \left(X_{ijkl} - X_{jikl} \right) &\left\{ \begin{array}\\ = Q_{kl} \text{ if $i$ is the location of producer k} \\ = -Q_{kl} \text{ if $i$ is the location of consumer k} \\ 0 \text{ otherwise} \end{array} \right\} \forall \; i,k,l\\ \end{align}

The final constraint ensures that internal nodes along a path have the same number of incoming and outgoing routes, producers have more outgoing than incoming routes, and consumers have more incoming than outgoing routes. It is a variation on the constraint found on wikipedia that has been adjusted to allow for multiple routes between producer/consumer pairs: https://en.wikipedia.org/wiki/Shortest_path_problem#Linear_programming_formulation.

Objective Function

The objective is relatively simple compared to the constraints: simply minimize costs. For the traffic, I assume that the traffic costs are proportional to the quantity $X$ (or $X^2$), rather than the actual number of trucks that you might use to deliver them. If this well-approximates the actual application, then the following objective function should work reasonably well.

\begin{align} roadCost &= \sum_{i,j}\left(\sum_{k,l}X_{ijkl}\right)\left(L_{ij} + \left(\sum_{k,l}X_{ijkl}\right)c_{ij}\right)\\ \\ efficiencyCost &= \sum_{k,l} Q_{kl}/e_{k} \\ \\ \min_{X,Z,Q,P} \;\; &roadCost + efficiencyCost \end{align}

Solving

Due to the unfortunate quadratic term, this is a mixed integer-quadratic programming problem. Fortunately, there are good solvers out there for these (I am currently using Gurobi 7.0, which is expensive, but not for academics).

I implemented it in Julia (0.5) using the JuMP package, which allows for very straightforward model specification, and it hooks into a wide variety of different commercial and open-source solvers.

If for some reason you're intent on writing your own solver, you'd need a QP solver as a primitive and then do the usual branch-and-bound algorithm on the integer variables. I highly recommend that you not do this.

Visualization

In Julia, there is the GraphPlot package which seems ideally suited to this. I haven't played with it much, but it seems well-suited to visualizing these sorts of flow problems. https://github.com/JuliaGraphs/GraphPlot.jl

I can't really say much more about what you should visualize except to point you to the GraphPlot tool above that will let you do pretty much anything you want. I put some examples using it for this problem in my implementation, which you can get to below.

My Implementation

I have put a html version of the IJulia notebook for solving this problem up as a gist, which can be found here: https://gist.github.com/tjolsen/ea9c677f43b19df482a2ee344f5d467c

To actually see it (rather than the source html), simply download the raw text as an html file and open it in your browser.

For a large-scale version of this, you would want to explicitly exploit the sparsity of $\mathcal{A}$ to reduce the number of $X$ variables. I didn't do that here, since I set it up for a 2-producer, 1-consumer network.