Last Mile Delivery From Multiple Depots in Python

Mathematical Modeling, Solution, and Visualization Using PuLP and VeRoViz

With the rapid growth of online shopping, companies are facing ever-increasing demands for speedy, low-cost delivery. Last mile delivery refers to the final stage of the supply chain, where packages are delivered from a depot to the customer’s doorstep. This is a complex tactical problem that involves jointly determining how to assign packages to trucks and how to route the trucks to customers. It is also a very expensive problem, with recent estimates placing last mile delivery at 53% of the total shipping cost. This underscores the need to generate efficient delivery plans.

The classic form of this problem involves a single depot (usually a warehouse) from which all trucks are loaded and sent out on their deliveries. A more complex version involves multiple depots in close proximity to one another — for example, when retail chains deliver from store locations. In this case, a given customer may be served by more than one depot, so the company must also determine which depots will ship to which customers. Sometimes no single depot will have all the items in a customer’s order available, requiring the order to be split among multiple depots.

Below we will discuss how to model and solve this more complex multi-depot problem form using integer programming (IP). This problem has the following aspects:

1. There is a set of trucks, depots, customers, and products.
2. Each customer has ordered a specific quantity of each product, and each depot has a certain quantity of each product available.
3. Each truck is based at exactly one depot (meaning its route always begins and ends at its base). Moreover, trucks need not be identical — each truck may have a different volume capacity and cost per mile.

The objective is to simultaneously determine 1) the products to be shipped from each depot to each customer, 2) how to assign packages to trucks, and 3) how to route each truck to its customers, all in a way that achieves the lowest total delivery cost possible.

We will implement and solve an IP model with PuLP and use VeRoViz to visualize the truck routes. To begin, we import the necessary libraries:

An Example Scenario

A furniture company has two depots in the Fredericksburg, VA area with eight customer orders to be delivered. The data and map are shown below. Note: The nodesArray variable was prepared with the VeRoViz Sketch Tool, which enables graphical creation of location data and exports to Python.

Modeling the Problem

While there are a number of ways one may approach this problem, we will build and solve an integer programming model. This gives a precise mathematical specification of the problem and allows problem instances of moderate size to be solved optimally using off-the-shelf solvers (though beyond our scope, larger instances often cannot be solved quickly with off-the-shelf solvers and require specially-designed solution algorithms). We begin with the model inputs:

Next, we define our decision variables:

Finally, we define the optimization model:

In this model, the objective function (1) that we want to minimize is simply the sum of all travel costs incurred. Constraints in (2) ensure that for each location, if a particular truck arrives at the location, then the truck also departs. Constraints in (3) ensure that no truck departs from a depot that is not its base. Constraints in (4) ensure that each customer gets all of the products they ordered. Constraints in (5) ensure no sub-circuits occur in any route. Since a group of locations forming a circuit will have the same number of edges as nodes, we prevent this from occurring in every possible nonempty subset of customers for each truck. Constraints in (6) ensure that for each depot and product, the total units of the product loaded onto trucks and shipped to customers from that depot does not exceed the availability at the depot. Constraints in (7) ensure that no units of any product are loaded onto a truck and shipped to a customer unless the truck visits the customer. Constraints in (8) ensure that for each truck, the total volume of products loaded aboard does not exceed its capacity. Finally, constraints in (9– 10) specify the domains for the decision variables (binary for the x variables; non-negative integer for the u variables).

For ease and reusability, we will create a Python function to construct instances of this model for specific input data using PuLP:

Solving the Example Scenario Problem

Now that we have the model formulated, we can use it to find an optimal solution for our scenario. Below we use the CBC solver that is included with PuLP. This may take 15–45 seconds to find an optimal solution. If you have access to the more powerful CPLEX solver, you can use the commented-out lines instead to get a solution much faster.

Running this gives us the following output message:

Extracting and Viewing the Truck Itineraries

Now we need to extract the truck itineraries from the decision variables in the solved model. For each truck, we want to know its stops and which products to deliver at each stop. To get this information, we need to sift through the non-zero decision variables.

This constructs the following truck itineraries:

Note that customer C1 is visited by two trucks (T2 and T4) — hence, a split order. Given the simultaneous customer demands and resources available, this turns out to be an optimal decision. This may also be necessary when, for instance, an order contains a set of items not found at any single depot.

Visualizing the Truck Routes

As our last step, we use VeRoViz to create a nice visualization for the truck routes:

Conclusion

Although many variations on this problem are possible, this example illustrates how we can model and solve such a problem using integer programming. It also shows how Python can be used to glue together powerful components such as PuLP and VeRoViz to create useful decision support systems quickly. Happy delivering!

Source code can be viewed in a notebook here or downloaded here.

Last Mile Delivery From Multiple Depots in Python Republished from Source https://towardsdatascience.com/last-mile-delivery-from-multiple-depots-in-python-26c4325407b4?source=rss—-7f60cf5620c9—4 via https://towardsdatascience.com/feed

<!–

–>