A New Variant of the Rich Vehicle Routing Problem in Industry 4.0 - the Mobile Production Vehicle Routing Problem: Models, Algorithms and Applications

Wang, Yu (2023) A New Variant of the Rich Vehicle Routing Problem in Industry 4.0 - the Mobile Production Vehicle Routing Problem: Models, Algorithms and Applications. PhD thesis, University of Liverpool.

Text 201254404_October2023.pdf - Author Accepted Manuscript Access to this file is embargoed until 1 January 2025. Download (4MB)

Abstract

With the rapid development of digital techniques, the world is now experiencing the era of Industry 4.0. In this era, there is a trend to apply digitized production to reduce operations costs such as inventory and transportation costs and, at the same time, meet customers' increasing need for prompt service and customized products. 3D printing is one of the most popular digitized production tools and is continuously upgrading. With the purpose of saving operation costs and improving service quality, Amazon filed a patent for an innovative logistics mode where vehicles equipped with 3D printers carry out production on the way to customers. To study the advantage of this new logistics mode, this research proposes a new variant of the vehicle routing problem: the mobile production vehicle routing problem (MoP-VRP). In this problem, vehicles are equipped with mobile factories, and production takes place on the way to the customer. The objective is to minimize the weighted cost incurred by travel and delay of service. The research was conducted in three stages: (1) a Mixed Integer Programming (MIP) model is formulated, and a meta-heuristic algorithm, the Adaptive Large Neighbourhood Search (ALNS), is developed for the MoP-VRP. To show the advantage of mobile production, the MoP-VRP is compared with the Central Production Vehicle Routing Problem (CP-VRP), where production takes place at a central depot. This research also proposes an efficient ALNS for the CP-VRP. (2) an exact algorithm, a branch-and-price algorithm, is developed. This research develops an efficient dominance test and proposes three heuristic algorithms to accelerate the process of solving the pricing problem. (3) the research also studies the Dynamic MoP-VRP (DMoP-VRP), where new requests are revealed over time, and the production and delivery plan has to be updated as new orders appear. Waiting strategies for both DMoP-VRP and Dynamic CP-VRP (DCP-VRP) are designed to improve the solutions. The DMoP-VRP is also compared with the DCP-VRP to show the superiority of mobile production in a dynamic setting. To conduct the experiment, this research generates benchmark instances based on Vehicle Routing Problem with Time Windows (VRPTW) benchmark instances and realistic instances based on a case study in Copenhagen. The real-life data is provided by the Danish Company 3D Printhuset. The main findings of the computational results are: (1) the proposed ALNS for both problems are efficient and can provide near-optimal solutions for instances of up to 200 customers within a short computational time. The comparison of the two problems shows mobile production's economic efficiency and flexibility. Mobile production can shorten the lead time, and at the same time, lower delivery costs. Moreover, long-term cost estimations show that this technology has low operation costs and thus has a bright future to be used in real-life practice. (2) The branch-and-price algorithm can solve all the 10/15/20 customer instances and most of the 25 customer instances to optimality. It can solve more instances than CPLEX within a much shorter time and provide better upper bounds than ALNS as the number of customers increases. (3) letting machines keep producing and vehicles wait can reduce the overall cost of the MoP-VRP. Compared to central production, using mobile production reduces the total cost by over 30\% across all scenarios and up to 42\% for highly dynamic problems (90\% of dynamic customers). With the proposed algorithm, the lead time can be quite short in highly dynamic cases (e.g., 80 minutes on average) and the delay can be controlled within only four minutes above the unavoidable delay for each customer.

Item Type:	Thesis (PhD)
Uncontrolled Keywords:	Vehicle Routing, Mobile Production, Meta-heuristics, Branch-and-price, Dynamic Vehicle Routing, Waiting Strategy
Divisions:	Faculty of Science and Engineering > School of Physical Sciences
Depositing User:	Symplectic Admin
Date Deposited:	30 Jan 2024 10:11
Last Modified:	30 Jan 2024 10:11
DOI:	10.17638/03173616
Supervisors:	Wen, Min Konstantopoulos, Takis Wu, Zili Song, Dongping
URI:	https://livrepository.liverpool.ac.uk/id/eprint/3173616