Data-centric solution methodologies for vehicle routing problems

Data-driven decision making has become more popular in today’s businesses including logistics and vehicle routing. Leveraging historical data, companies can achieve goals such as customer satisfaction management, scalable and efficient operation, and higher overall revenue.

In the management of customer satisfaction, logistics companies use consistent assignment of their drivers to customers over time. Creating this consistency takes time and depends on the history experienced between the company and the customer. While pursuing this goal, companies trade off the cost of capacity with consistency because demand is unknown on a daily basis. We propose concepts and methods that enable a parcel delivery company to balance the trade-off between cost and customer satisfaction. We use clustering methods that use cumulative historical service data to generate better consistency using the information entropy measure.

Parcel delivery companies route many vehicles to serve customer requests on a daily basis. While clustering was important to the development of early routing algorithms, modern solution methods rely on metaheuristics, which are not easily deployable and often do not have open source code bases. We propose a two-stage, shape-based clustering approach that efficiently obtains a clustering of delivery request locations. Our solution technique is based on creating clusters that form certain shapes with respect to the depot. We obtain a routing solution by ordering all locations in every cluster separately. Our results are competitive with a state-of-the-art vehicle routing solver in terms of quality. Moreover, the results show that the algorithm is more scalable and is robust to problem parameters in terms of runtime.

Fish trawling can be considered as a vehicle routing problem where the main objective is to maximize the amount of fish (revenue) facing uncertainty on catch. This uncertainty creates an embedded prediction problem before deciding where to harvest. Using previous catch data to train prediction models, we solve the routing problem a fish trawler faces using dynamically updated routing decisions allowing for spatiotemporal correlation in the random catch. We investigate the relationship between the quality of predictions and the quality of revenue generated as a result.