June 2022 Update: the official paper is published online! https://pubsonline.informs.org/doi/abs/10.1287/opre.2022.2304 If you find the source code useful in your research work, please cite: Ledvina, Kirby, et al. "A new approach for vehicle routing with stochastic demand: Combining route assignment with process flexibility." Operations Research (2022).

September 2021 Update: rotational overlapping strategies implemented; it can be regarded as an enhanced version of the original overlapping strategies, inspired by the close chains in process flexibility.

flexible-routing

The flexible-routing repository contains simulation code and output files to computationally assess the costs of a vehicle routing strategy with fixed routes and customer sharing. This work improves on the simulation study in the working paper by Ledvina et al. (2020) and serves as supplemental files for Kirby Ledvina's master's thesis in MIT's Department of Civil and Environmental Engineering.

Overview

We explore vehicle routing with customer sharing as a strategy to accomodate new and variable customer demands in distribution networks with fixed delivery routes. For this setting, we propose predesigning routes with some overlap such that adjacent routes share customers. This design gives the delivery fleet operator the flexibility to assign drivers to subsets of their predesigned routes in response to realized customer demands.

We define four alternative strategies for designing and executing routes with varying degrees of flexibility: dedicated routing, overlapped routing, full flexibility, and reoptimization. The Jupyter notebook routing_examples.ipynb describes and illustrates these routing strategies for a randomly generated example problem. Please see Ledvina et al. (2020) for a formal description of our routing model.

Contents

This repository includes simulation code (Python), output data and figures, and an R script for creating summary figures from the data. Files include lightly edited code blocks from Google OR-Tools for the routing optimization steps (the TSP and VRP solvers).

Code Files

• simulate.py - defines new scenarios, runs the simulation, and saves the simulation's output as a single .xlsx file in the output/ subfolder
• supporting.py - includes supporting code such as functions to execute routing algorithms and calculate transportation costs
• combine_outputs.py - combines simulation output files from the /output subfolder into a single summary .xlsx sheet
• create_figures.R - reads in all files in the output/ subfolder and generates summary graphs

Also, the Jupyter notebook routing_examples.ipynb is a supplemental file that allows users to generate a random customer and demand instance and see the resulting routes and costs under the different routing strategies.

Output Files

• output/ - subfolder with output files generated by simulate.py through individual simulation runs.*
• combined_outputs_2020-10-23.xlsx - the most recent compilation of simulation results. Generated by combine_outputs.py.
• figures/ - subfolder with summary figures generated by create_figures.R

*Note: We structured our simulation runs so that each file in output/ covers a unique scenario.

Running Simulations

Requirements

The simulation code runs with Python 3.7. You need the Pandas and Numpy packages. You also need to install Google OR-Tools within your Python version by following these instructions.

Running simulate.py

You will need to edit simulate.py directly to specify the scenario details as well as problem sizes and number of random instances to generate. A scenario defines several network parameters, namely primary route size, overlap size, vehicle capacity, and customer demand distribution. The code is set up to easily accomodate the following scenarios:

Open simulate.py in a code editor. Scroll down in the file until you can find the following line:

results = simulate(scenario = 'baseline', problem_sizes = [5,10,20,40,80], capacity = 20, route_size = 5, overlap_size = 5, cust_sims = 30, dem_sims = 200)

The function simulate takes in several arguments. The arguments "capacity", "route_size", and "overlap_size" are routing problem parameters that refer to vehicle capacity, number of customers in the primary route, and number of customers shared by adjacent extended routes, respectively. Please see the Jupyter notebook for an explanation of these terms. Then the following terms are simulation parameters:

• "problem_sizes" - a list with all numbers of customers to loop through and simulate
• "cust_sims" - the number of random customer location instances to create
• "dem_sims" - the number of random demand instances to assign to each customer instance

So for a simulation with problem sizes [5,10,20,40,80], cust_sims of 30, and dem_sims of 200, we calculate routing costs for 600 unique customer/demand combinations for networks with 5 customers, another 600 unique customer/demand combinations for networks with 10 customers, and so on.

Finally, "scenario" is (1) the label assigned to all rows of output data and (2) a flag for the customer demand distribution. By default, all predefined scenarios and newly defined scenarios will draw each customer's demands uniformly from 0, 1, ..., 8 except for the preexisting Binomial Demand scenario and the Stochastic Demand scenario. See the section below on defining new demand distributions if you wish to create a scenario with a demand distribution other than the baseline's Uniform{0,8}.

Edit the simulate() arguments as desired. Then scroll to the bottom of the file and update the code block

timestamp = time.strftime("%Y-%m-%d_%H-%M-%S")
outfile = 'output/results_{}.xlsx'.format(timestamp)
with pd.ExcelWriter(outfile) as writer:
    results.to_excel(writer, sheet_name = 'baseline')
    [...]

with your desired output file path and Excel sheet names. The output is an Excel workbook with a sheet containing average transportation costs and trip counts for the dedicated, overlapped, full flexibility, and reoptimizatiton strategies across all instances for each problem size. We also save the standard deviation, 5th percentile, and 95th percentile outcomes as separate sheets in this workbook. The output file name includes the simulation's completion time.

Save and close simulate.py.

You can now run simulate.py from the command line or other Python interpreter. Note that simulate.py does NOT have a command line interface, which is why we needed to directly edit the file as described in the section above.

Defining new demand distributions

For any simulation run, each customer's demand by default follows a Uniform{0,8} distribution, i.e., is drawn from 0, 1, ..., 8 with equal probability. To define a simulation with a distribution OTHER THAN this default, follow the steps below:

1. Open simulate.py and update or create a new line that calls the function simulate() as described above.

2. Choose a scenario label and set the "scenario" argument in the simulate() call equal to this name.

3. Save and close simulate.py.

4. Open supporting.py and find the function create_instances(). The function should be around line 446.

5. The function create_instances() contatains two inner functions: gen_new_instances() and update_demands(). You will need to make the same change in both of these inner functions.

6. In gen_new_instance(), find the following code block

    # Generate demands depending on scenario
    if scenario == 'stochastic_customers':
        # Equal probability of selecting 0 or 8
        new_dems = list(np.random.choice([0,8], num_cust))
    elif scenario == 'binomial':
        # Binomial(8,0.5) distribution
        new_dems = list(np.random.binomial(8, 0.5, num_cust))
    else:
        # Uniformly distributed between 0 and 8
        new_dems = list(np.random.randint(0, 8, num_cust))
   

and update as needed so that if "scenario" equals your scenario label from step 2, "new_dems" is set to a list of numbers (integers or floats) of length "num_cust".
7. Make the same change to the identical code block in function update_demands().
8. Save and close supporting.py.

You can now run simulate.py with your new scenario.

Contributors

• Kirby Ledvina, MIT Data Science Lab, kirby.ledvina@gmail.com
• Hanzhang Qin, MIT Data Science Lab, hqin@mit.edu
• Prof. David Simchi-Levi (Advisor), MIT Data Science Lab, dslevi@mit.edu
• Prof. Yehua Wei, Duke Fuqua School of Business, yehua.wei@duke.edu