Variable neighborhood search based approaches to a vehicle scheduling problem in agriculture

• DOI: http://doi.org/10.1111/itor.12480
• Author: Zorica Stanimirović,Đorđe Stakić,Ana Anokić,Tatjana Davidović
• Date: 01 January 2020
• Published date: 01 January 2020

Intl. Trans. in Op. Res. 27 (2020) 26–56

DOI: 10.1111/itor.12480

INTERNATIONAL

TRANSACTIONS

IN OPERATIONAL

RESEARCH

Variable neighborhood search based approaches to a vehicle

scheduling problem in agriculture

Ana Anoki´

ca, Zorica Stanimirovi´

cb, Tatjana Davidovi´

ccand Đorđe Staki´

cb

aFaculty of Agriculture, University of Belgrade,Nemanjina 6, 11 080, Zemun Belgrade, Serbia

bFaculty of Mathematics, University of Belgrade, Studentski trg16/IV, 11 000, Belgrade, Serbia

cMathematical Institute, Serbian Academy of Science and Arts, KnezaMihaila 36, 11000, Belgrade, Serbia

E-mail: anokicana@agrif.bg.ac.rs [Anoki´

c]; zoricast@matf.bg.ac.rs [Stanimirovi´

c]; tanjad@mi.sanu.ac.rs [Davidovi´

c];

djordjes@matf.bg.ac.rs [Staki´

c]

Received 5 February2017; received in revised form 26 August 2017; accepted 8 October 2017

Abstract

A vehicle scheduling problem (VSP) that arises from sugar beet transportation within minimum working

time under the set of constraints reflecting a real-life situation is considered. A mixed integer quadratically

constrained programming (MIQCP) model of the considered VSP and reformulation to a mixed integer

linear program (MILP) are proposed and used within the framework of Lingo 17 solver, producing optimal

solutions only for small-sized problem instances. Two variants of the variable neighborhood search (VNS)

metaheuristic—basic VNS (BVNS) and skewed VNS (SVNS) are designed to efficientlydeal with large-sized

problem instances. The proposed VNS approaches are evaluated and compared against Lingo 17 and each

other on the set of real-life and generated problem instances. Computational results show that both BVNS

and SVNS reach all known optimal solutions on small-sized instances and are comparable on medium- and

large-sized instances. In general, SVNS significantly outperforms BVNS in terms of running times.

Keywords:vehicle scheduling problem;transportation of agriculture rawmaterials; mixed integer quadratically constrained

programming; metaheuristics; variable neighborhood search

1. Introduction

This study is motivated by a real-life problem of optimizing sugar beet transportation in a sugar

factory in Serbia. Sugar beet is an agricultural raw material with a very low price on the market

and major costs in sugar production arise from transportation. Therefore, even a small percentage

of savings that can be made in this early production phase is very important. Large companies that

purchase raw materials from individual producers have an important task to keep them as business

associates, and therefore, companies usually take over all transportation costs. The company rents

vehicles and hires workersfor transport, loading and unloading of sugar beet. An efficient transport

C

2017 The Authors.

International Transactionsin Operational Research C

2017 International Federation ofOperational Research Societies

Published by John Wiley & Sons Ltd, 9600 Garsington Road, Oxford OX4 2DQ, UK and 350 Main St, Malden, MA02148,

USA.

A. Anoki´

c et al. / Intl. Trans. in Op. Res. 27 (2020) 26–56 27

organization that satisfies all problem-specific constraints with minimum expenditure of time and

money may significantly increase profit in the sugar industry.

The harvesting season of sugar beet in Serbia begins in September and lasts till December,

sometimes January. For each date in the season, the list of locations with the amounts of collected

goods is prepared in advance. In order to avoid the loss of quality, collected sugar beet should

not stand in the open for too long. Sometimes the weather conditions, such as the upcoming rain,

force the producers to prepare the goods a few days before or after the agreed date, and therefore,

the plan needs to be updated on a daily basis. The locations where the goods are kept in the open

for more than a predetermined number of days are considered as urgent and they must be served

during the day. For an urgent location, it is not important how much the stowage time exceeds the

predetermined number of days. Another important condition is to satisfy the daily factory needs,

regarding the required amount of goods. Once the factory machines start to work they should not

stop, as the starting process is very expensive.

Vehicles used for transportation are homogeneous in the sense of capacity and average velocity.

They are located at the factory area, which is the starting and the finishing point for each vehicle.

In each tour, a vehicle serves only one location and returns to the factory. Vehicles do not make

routes in order to preventthe possibility to obtain a low-quality mixture of sugar beet from different

locations. In addition, the quantities of sugar beet collected at each location significantly exceed

vehicle’s capacity, and therefore, each location has to be visited several times in order to be emptied.

A vehicle departs from a location fully loaded, and only the last vehicle that serves a location may

be not full with goods. When a vehicle with loaded sugar beet arrives to the factory area, a certain

time is needed for unloading the goods including the analysis of samples,and after that a vehicle can

start a new tour. At each location with collected goods, two vehicles cannot be loaded in the same

time because there is only one loading machine available. For this reason, the difference in arrival

times of two different vehicles at a location must not be smaller than the duration of loading. On

the other hand, it is assumed that the factory has enough labor, machines, and space for handling

a limited number of vehicles. At the factory area, the queues of vehicles loaded with goods are not

allowed. The objective is to find the set of vehicle schedules that minimizes the required working

time, that is, the moment of time when all vehicles finish their tours.

The characteristics of the considered problem are summarized as follows:

rvehicles are homogeneous and used several times during the day (multiple trips);

rthe factory is the starting and ending point of each vehicle tour (single depot);

reach vehicle serves only one location in each tour;

rdaily factory needs, regarding the amount of delivered goods, must be satisfied;

rthere is a limit on the number of days that the goods can stay in the open;

rurgent locations must be served during the working day;

rtwo vehicles cannot be loaded at the same location at the same time;

rat the factory area, a limited number of vehicles can be unloaded at the same time;

rthe queues of vehicles are not allowed either at a location for loading or at the factory area for

unloading;

rthe objective is to minimize the moment of time when all vehicles finish their tours.

The considered problem is first formulated as a mixed integer quadratically constrained pro-

gramming (MIQCP) model and then a reformulation to a mixed integer linear program (MILP) is

C

2017 The Authors.

International Transactionsin Operational Research C

2017 International Federation of OperationalResearch Societies