Developing New Tools for Efficient Solutions to Large-Scale Vehicle Routing Problems with Delivery Deadlines

Examples abound in Oman of businesses that employ a fleet of vehicles to transport products from a central depot or warehouse to multiple customers located in various geographic regions. Deciding the routes that each vehicle will follow in completing service to all the customers within a given delivery deadline is a NP-hard problem, optimal solutions for which are difficult for problems that have large numbers of customers. The aim of this research project is to develop mathematical models that can solve large scale vehicle routing problems with a single deadline (VRP+1D) to optimal results in significantly less computation time than currently available models. The reduction of computation time enables managers to maintain updated and efficient distribution routes and schedules, leading to reductions in costs, road congestion and carbon emissions. The solution approach is based on developing heuristic that exploit the sparse nature of road networks with the aim of generating smaller, more manageable models that can be solved optimally in acceptable computation time. This result will lay the groundwork for an interactive software tool that allows managers to assess different strategies in adopting vehicle routing schedules within the framework of a firm?s supply chain. The practical contributions of this project shall be evaluated by application to a selected logistics business in the city of Muscat, Oman