Embedded Vehicle Routing Problem: A Modeling and Optimization Framework for Real-World Multi-Purpose Truck Network

Abstract

This paper introduces original contributions to the field of vehicle routing problems, specifically addressing the optimization of multi-purpose truck routing within the agricultural third-party logistics domain. The study presents a novel approach aimed at optimizing the routing of a 3PL provider’s truck fleet, considering efficient commodity delivery and hygienic practices for transporting agricultural products. To tackle the complexities associated with multi-purpose truck routing, we propose the concept of the Embedded Vehicle Routing Problem (EMBDD-VRP). The EMBDD-VRP adopts a two-phase framework, embedding multiple local Vehicle Routing Problems (VRPs) into a global VRP structure. By leveraging existing VRP solutions in each phase, the EMBDD-VRP retains the desirable characteristics of classical VRP models while effectively addressing the unique challenges faced by 3PL providers. Case studies and practical implementations conducted within the Thai agriculture sector demonstrate the applicability and viability of the proposed methodology. Compared to the exact VRP method, our analysis shows that the proposed EMBDD-VRP reduces the search space size by approximately 100-fold for medium-sized problems. The computational results indicate that the solution gap between EMBDD-VRP and the exact VRP method (using Gurobi) ranges from 0% to 6.2% in the simplified problem, where the exact VRP is applicable. While the exact method becomes infeasible for more complex problems, EMBDD-VRP can efficiently solve much larger instances, including real-world cases. This research not only fills gaps in the literature but also offers a promising avenue for optimizing multi-purpose truck routing within agricultural third-party logistics operations.

Keywords

• Multi-purpose truck routing
• tabu search
• third-party logistics
• vehicle routing problems