Modeling and solving a multi-trip multi-distribution center vehicle routing problem with lower-bound capacity constraints

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.