This accelerator provides the code template for solving large-scale route optimization problems. The accelerator implements a scalable optimization approach that partitions a large optimization problem into smaller problems, and solves those reduced optimization problems in parallel by leveraging Azure Machine Learning. The solutions to the smaller problems are then consolidated to form a feasible solution to the original optimization problem. A real-world route optimization scenario is used as an example to demonstrate the use of the accelerator.

The example demonstrated in this solution accelerator is inspired by a real-world optimization scenario. The customer is a manufacturing company. They have warehouses in different locations. When they receive orders from their clients, a planner need to plan the item-to-truck assignment for order delivery. The planner also need to decide the route of each delivery truck, namely, the sequence of the stops to deliver orders to different destinations. A delivery assignment has its associated cost determined by the type of the assigned delivery truck and the corresponding travelling distance. The optimization objective here is to minimize the overall delivery cost.

This is a variant of the vehicle routing problem (VRP). The constraints modeled in our example are:

1. There are different types of trucks we can choose from. A truck has capacity limit on both area and weight. (We assume that there is no limit on the number of trucks for each type)
2. An item is only available by a specific time. A truck can start only when all items assigned to it are available.
3. The available time difference between the earliest and last available items in the same truck should be less than a user defined limit (e.g., 4 hours).
4. All items need to be delivered to their destinations before their deadlines.
5. Depending on the properties of products, some items can put in the same truck, but some cannot.
6. A truck can have at most N stops, where N is a user defined number.
7. A truck need to stay at each stop for M hours to unload the items, where M is a user defined number. Each stop will incur a fixed amount of cost in addition to the delivery cost.

Below shows an example input of the route optimization problem. It is a set of items to be delivered, where the Item_ID uniquely defines an item.

Also assume there are 3 types of trucks available for assignment:

Below is an example output of the route assignment, where Truck_ID uniquely defines a truck. The column Shared_Truck indicates if there are items from different orders sharing the same truck.

The key idea of this accelerator is to implement a general framework (illustrated by the below figure) for solving large-scale route optimization problems. The end-to-end pipeline is implemented using Azure ML pipeline consisting of 4 key steps. The complete definition of the pipeline can be found in this notebook.

We use the following simplified example to illustrate the above steps. Assume we have a set of orders as below, where we group same type (namely, having same Material_ID) of items from the same order as a single record for ease of discussion.

For large-scale route optimization problems, it is often possible to apply human heuristics to pre-assign a subset of the items, effectively reducing the problem size. In some cases, we can easily find an optimal/near-optimal assignment based on simple heuristics. For example, in the above route optimization scenario, there are different types of trucks we can choose from. Among them, the biggest truck (i.e., the 10t one) is most cost effective. A simple heuristic is to fill up the biggest truck with items of the same destination. This assignment incurs the lowest delivery cost for those items.

For example, we can apply the above heuristic to our original input and obtain the following two outcomes:

• a partial result that contains the heuristic assignment:

• the remaining unassigned items as the input for the partition step (you may compare it with the original input of the reduce step):

Given the reduced problem from step 1, we can apply different partition strategies to further reduce the problem space. The objective is to ensure each single partition is small enough to solve within a user defined time limit. In an ideal case, the chosen partitioning strategy should not change the optimum of the original problem. Using the above route optimization problem as an example, partitioning the items by the delivery source as below will not change the optimum of the original problem:

• items starting from Source S1:

• items starting from Source S2:

In the case where there are a lot of items from the same source, you may need to further partition those items such that individual problems can be solved within a given time limit. The optimality may not be guaranteed in this case.

For example, we can further partition items from source S1 by Available_Time. The intuition is that the business constraint #3 of our problem restricts the time span of all the items in the same truck. So, grouping items with similar available time will be easier to satisfy this constraint. Below are two example partitions to illustrate the idea.

• Orders that are available on 2022-08-01:

• Orders that are available on 2022-08-02:

This step is achieved by the ParallelRunStep function provided by Azure Machine Learning. The ParallelRunStep function can be configured to solve partitioned optimization problems in parallel with a chosen optimization solver.

There are many optimization techniques, e.g., Linear Programming (LP), Mixed Integer Programming (MIP), Constraint Programming, etc. that one can use to solve the optimization problems. The framework introduced in this accelerator is solver-agnostic. In this accelerator, we demonstrate the use of Constraint Programming for route optimization.

Comparing to mathematical optimization techniques (e.g., LP, MIP), Constraint Programming is more expressive in that it can be used to model optimization problems in forms of arbitrary constraints; for more details see this article.

Once all the smaller problems are solved, we can merge their corresponding solutions with the partial result produced in step 1 to form a feasible solution to the original optimization problem. Assume we have solved two smaller problems with their individual results as follows:

• Result for partition 1:

• Result for partition 2:

We can simply concatenate the above results to form the final solution:

The below sections describe the detailed steps to run the accelerator.

You need to have an Azure subscription with the access to the following resources:

1. Create a virtual environment. The solution accelerator is tested with Python 3.8.

   conda create -n route-optimization python=3.8
   conda activate route-optimization
   

2. Clone the repo and install python dependencies:

   git clone https://github.com/microsoft/dstoolkit-route-optimization.git
   cd dstoolkit-route-optimization
   pip install -r requirements.txt
   

   If you are using Visual Studio Code, you will find a kernel named route-optimization in the kernel list. If you want to use Jupyter Notebook instead, create a kernel explicitly:

   python -m ipykernel install --user --name route-optimization --display-name "route-optimization"
   

3. Upload sample data

   We have prepared some sample input data in the sample_data directory. You need to upload all the data to the default Datastore in your Azure ML workspace. The order_small.csv under this directory is a small sample, best for testing. You can alternatively use order_large.csv to test parallel run. In addition, there is another file named distance.csv that stores the pair-wise distance between different locations.

   To find your default Datastore, you can login your Azure ML studio, and click on the Datastores icon:

   

   In the Overview page of the default Datastore, you can find the Blob container linking to this Datastore. Follow the link, you can go to the portal of the container, where you can upload the sample data.

   

   For example, below we create a folder named model_input and upload all the sample data into this folder.

   

4. Configure Environment Variables

   Create a .env file in the root directory of the repository, and fill in the values for the following variables (Note: .env is meant to be used in local mode. It is already added to the .gitignore file to avoid accidental commit of credentials to a repo):

   # Azure ML configuration
   AML_WORKSPACE_NAME=    # The name of the Azure ML workspace
   AML_SUBSCRIPTION_ID=  # The Azure subscription ID related to the above Azure ML workspace
   AML_RESOURCE_GROUP=     # The resource group of the Azure ML workspace
   

5. Run the optimization pipeline

   You can now create and run the whole pipeline using the notebook for pipeline definition. Once the pipeline run is completed, it will output the final route assignment as a csv file to the Azure ML default Datastore under the output path you specified in the notebook (e.g., model_output in our above example).

├── ./notebook
│   ├── ./notebook/aml_pipeline.ipynb     # Notebook for optimization pipeline
├── ./requirements.txt                    # Defines required libraries in Python
├── ./sample_data
│   ├── ./sample_data/distance.csv        # Sample data defining distances between locations
│   ├── ./sample_data/order_large.csv     # Large example of customers' orders
│   └── ./sample_data/order_small.csv     # Small example of customers' orders
├── ./src
│   ├── ./src/core
│   │   ├── ./src/core/logger.py          # Defines logging features
│   │   ├── ./src/core/merger.py          # Defines logic for merging the partitioned problem result
│   │   ├── ./src/core/model.py           # Defines the modelling logic and the core optimizaiton problem
│   │   ├── ./src/core/partitioner.py     # Defines the partition strategy
│   │   ├── ./src/core/reducer.py         # Defines any heuristic for search space reduction
│   │   └── ./src/core/structure.py       # Defines basic data structure
│   ├── ./src/merge.py                    # Wrapping script for merge process
│   ├── ./src/partition.py                # Wrapping script for partition process
│   ├── ./src/reduce.py                   # Wrapping script for reduce process
│   └── ./src/solve.py                    # Wrapping script for solve process
└── ./tests
    └── ./tests/core                      # Test codes for each process

This project welcomes contributions and suggestions. Most contributions require you to agree to a Contributor License Agreement (CLA) declaring that you have the right to, and actually do, grant us the rights to use your contribution. For details, visit https://cla.opensource.microsoft.com.

When you submit a pull request, a CLA bot will automatically determine whether you need to provide a CLA and decorate the PR appropriately (e.g., status check, comment). Simply follow the instructions provided by the bot. You will only need to do this once across all repos using our CLA.

This project has adopted the Microsoft Open Source Code of Conduct. For more information see the Code of Conduct FAQ or contact [email protected] with any additional questions or comments.

This project may contain trademarks or logos for projects, products, or services. Authorized use of Microsoft trademarks or logos is subject to and must follow Microsoft's Trademark & Brand Guidelines. Use of Microsoft trademarks or logos in modified versions of this project must not cause confusion or imply Microsoft sponsorship. Any use of third-party trademarks or logos are subject to those third-party's policies.