A variant of Vehicle Scheduling Problem (VSP) arising from the sugar beet transportation in a sugar factory in Serbia is introduced. The objective of the considered VSP is to minimize the required transportation time under problem-specific constraints. The considered VSP is first modelled as Mixed Integer Quadratically Constrained Program (MIQCP) and then reformulated to the equivalentMixed Integer Linear Program (MILP). In addition, it is proved that the considered VSP is NP-hard. Both MIQCP and MILP formulations were used within the framework of Lingo 17 solver on the set of real-life and generated problem instances. The proposed formulations enable Lingo 17 solver to produce optimal or feasible solutions for smaller-size problem dimensions. On these test examples, MILP reformulation showed to be superior over the MIQCP model in terms of solution quality and running times required by Lingo 17 solver.

This is a joint work with Anokić Ana, Tatjana Davidović and Đorđe Stakić.