Modeling and solving a multi-trip multi-distribution center vehicle routing problem with lower-bound capacity constraints. (October 2022)

• Record Type: Journal Article
• Authors: Nguyen, Van Son; Pham, Quang Dung; Nguyen, Thanh Hoang; Bui, Quoc Trung
• Is Part Of: Computers & industrial engineering. Volume 172:Part A(2022)
• Publication Date: 2022-10
• Subjects: Routing -- Dairy product transportation -- Multi-trip multi-distribution center VRPTW -- Lower-bound capacity constraints; Engineering -- Data processing -- Periodicals; Industrial engineering -- Periodicals; 620.00285
• DOI: 10.1016/j.cie.2022.108597
• Languages: English
• ISSNs: 0360-8352

Abstract

Abstract: Vehicle routing problem (VRP) for delivering goods from distribution centers to customers is one of the main operations in logistics. Optimizing route plans for vehicles allows companies to save a huge amount of operational costs. The VRP problem is also one of the most studied problems in the domain of operations research. There are several variants of the VRP problem that have been considered in the literature. This paper proposes a new variant of the vehicle routing problem taking into account most of the well-studied features, especially with a new constraint on the lower bound of the capacity of vehicles which has not been investigated in the literature. The problem requirements come from one of the biggest dairy distribution companies in Vietnam. With over 1000 customer points included in a plan on average, the company takes at least one working day to make a route plan. We formulate the considered problem as a mixed-integer linear programming problem, analyze the challenges of the lower-bound capacity constraints and propose an adaptive large neighborhood search framework for solving it. Experimental results on large realistic and randomly generated instances show the efficiency and the applicability of the proposed method. The application of the proposed method led to the rapidity in generating the solution; this task that used to take one day is decreased to just two hours. Highlights: Describe a MILP model of a VRP with lower-bound capacity constraints. Analyze the challenges of lower-bound capacity constraints. Propose an adaptation of existing methods to handle the new capacity constraints. Propose an adapted ALNS algorithm for solving the given problem. Conduct experiments on realistic and random instances.