Delivery Route

Chicago,

USA

Location

September 2020 -

December 2020

Date

Andrew Patronick

Andy Balcazer

Role

Team

Heuristic Programming

Simulation

Optimization

Skills

Data Analysis

The North Suburban Library System (NSLS) is considering an alternate approach to the hub library system. Under the new plan, the delivery vans would visit all of the libraries, but reduce the frequency of visits depending on demand- assuming vehicle capacity is not a problem. Vehicle tour lengths are constrained by travel time, and that all 4 delivery vehicles are operational.

Minimizing Time: Routing

The heuristic algorithm will enable NSLS administration to operate 4-van routes that cover all of their 29 libraries locations.

 

The algorithm will determine the frequency that each van visits each library. In addition, the algorithm will determine the route for each van: what subsets of libraries will each van visit on each day of a week

Front pictures_auto_x2.jpg

Research

Assumption

Find the library capabilities and collect data information on the vehicle fleet

Mathematical Formulation

Provide a linear mathematical model with objective and constraints to solve for

Heuristic Solution

Heuristics offer fast and semi-optimal answers for the user and can be updated regularly

Assumptions

  • The maximum visiting frequency for each library is once per day (M/T/W/Th/F) and the minimum visiting frequency is:

    • 0 ≤ demand < 75  →  2: T, Th

    • 75 ≤ demand < 150  →  3: M, W, F

    • Demand ≥ 150  →  5: M, T, W, Th, F

      * Two Graphs below provide further details

  • A library currently visited on T/Th can be increased to M/W/F, and a library currently visited on M/W/F can have its frequency increased to every day.

  • Each stop at a library takes 10 minutes, regardless of demand. However, the travel time in between libraries depends on the distance given in the graph above.

  • Each day, every library can only be visited at most once. This means no 2 vans can visit the same library on a given day, and the assigned van cannot “travel past” the library it already visited.

  • The van-library pairing is not necessarily exclusive. This means different vans can be assigned to visit the same library, as long as they visit on different day groups (T/Th, M/W/F). For example, if ELA has a 5-day schedule, van A can visit on M/W/F while van B can visit on T/Th. 

  • All vehicles are the same and that there is no limit on any of the vehicles’ capacity.

Heuristic Solution

We developed a randomized greedy heuristic to find a near-optimal, feasible solution.

 


 
The heuristic will output all feasible solutions, including routes, total distance, and total frequency, determined over 10,000 iterations. The optimal solution is the one with the highest total frequency.
 

 


If there are multiple solutions with the same total frequency, the solution with the lowest total distance traveled should be chosen.

Heuristic Flow Chart

Mathematical Formulation

  • Sets:

    • I: Set 1 of all libraries

    • J: Set 2 of all libraries

    • K: Set of vans (K1, K2, K3, K4)

  • Parameters:

    • H: Maximum total driving time per vehicle per day (160 minutes)

    • S: Stop time at a library (10 minutes)

    • Fi: Minimum frequency of visits to library i

    • Tij: Travel time from library i to library j

  • Decision Variables:

    • Xi: Frequency of visiting library i

    • Yijk: Binary. 1 if vehicle k leaves library i to travel to library j on M,W,F; 0 otherwise

    • Wijk: Binary. 1 if vehicle k leaves library i to travel to library j on T,Th; 0 otherwise

  • Objective Function:

    • max sum{i in I} sum{j in J} Xij​

Heuristic Solution

Of the 10,000 scenarios, the heuristic identified 10 total possible solutions.

 

Of the 10, only 3 solutions are optimal (identified as a blue dot with a black outline). The three solutions identified had the best tradeoff between route times and library visit frequencies.

 

Ultimately, the solution with the highest frequency was selected as the most optimal solution in this space, as NSLS’s primary objective is to increase the frequency with which the vans visit each library.

Proposed Solution Library-visiting Schedule By Van

Takeaways

  • Heuristic solutions provide a semi-optimal solution as they cut down the run time of the program.

  • It is possible to find a slightly better solution with more than 10,000 iterations.

My Ventures

Stocks

Analyzing banks S&P 500 companies recommendations.  Surprisingly, there were no trackers following the performance of analyst picks over the long term and I decided to build one.

Logistics

Stroke Code

Redesigning the CODE stroke activation process to reduce the Door-in-door out time for stroke patients

PROJECT WILL BE AVAILABLE AUGUST 2021