Vehicle scheduling problem in sugar beet transportation - a general variable neighborhood search approach

Abstract

A variant of Vehicle Scheduling Problem (VSP) arising from the sugar beet transportation in a sugar factory in Serbia is presented. The objective of the considered VSP is to minimize the required transportation time under problem-specific constraints. The problem is first formulated as a Mixed Integer Quadratically Constrained Program (MIQCP) and then transformed to a Mixed Integer Linear Program (MILP). The proposed MILP model was used within the framework of CPLEX solver, which produced optimal solutions only for small-size problem instances. Therefore, a General Variable Neighborhood Search (GVNS) is designed to solve problem instances of larger dimensions. GVNS is evaluated and compared against CPLEX on the set of real-life and generated problem instances. Obtained computational results show that GVNS is a promising solution approach to VSP, as it is able to reach high-quality (mostly optimal) solutions within very short running times.