Beyond Sequencing Nodes: Unlocking The Profit Potential of Vehicle Routing Through Proactive Customer Engagement

AbstractThis paper explores how strategic customer engagement can significantly improve vehicle routing efficiency (by influencing the design of the routing set), particularly the demand-to-distance ratio. While existing routing algorithms excel at finding optimal routes for a given set of delivery points, they often overlook the crucial step of customer selection before all orders are finalized. Our study investigates the impact of distance- and demand-based customer selection after an initial set of orders has been placed. We utilized a well-established Hybrid Genetic Search (HGS) algorithm, specifically tailored for the Capacitated Vehicle Routing Problem (CVRP), to determine optimal routes across five distinct scenarios. These scenarios involved an initial random selection of 75 customers, followed by the addition of 50 more customers. The additional 50 were chosen based on different criteria: randomly, by highest demand, by shortest distance, or by the worst demand-over-distance ratio from the remaining pool of potential customers. Through one thousand simulated instances, our results consistently demonstrated that increasing the number of customers improved the demand-to-distance performance. Crucially, selecting customers based on their shortest distance exhibited a significantly steeper performance improvement compared to selection based solely on demand. This compelling evidence underscores that strategic customer addition plays a vital role in substantially enhancing vehicle routing efficiency.Keywords:Traveling Salesman Problem (TSP), Capacitated Vehicle Routing Problem with Time Windows (CVRPTW), Revenue Management, Demand Responsiveness, Online Grocery, Urban Logistics.