Professional article
English

A learning tabu search for a truck allocation problem with linear and nonlinear cost components

Published in

Naval Research Logistics (NRL), vol. 62, no. 1, p. 32-45

Publication date

2015

Abstract

The two-level problem studied in this article consists of optimizing the refueling costs of a fleet of locomotives over a railway network. The goal consists of determining: (1) the number of refueling trucks contracted for each yard (truck assignment problem denoted TAP) and (2) the refueling plan of each locomotive (fuel distribution problem denoted FDP). As the FDP can be solved efficiently with existing methods, the focus is put on the TAP only. In a first version of the problem (denoted (P1)), various linear costs (e.g., fuel, fixed cost associated with each refueling, weekly operating costs of trucks) have to be minimized while satisfying a set of constraints (e.g., limited capacities of the locomotives and the trucks). In contrast with the existing literature on this problem, two types of nonlinear cost components will also be considered, based on the following ideas: (1) if several trucks from the same fuel supplier are contracted for the same yard, the supplier is likely to propose discounted prices for that yard (Problem (P2)); (2) if a train stops too often on its route, a penalty is incurred, which represents the dissatisfaction of the clients (Problem (P3)). Even if exact methods based on a mixed integer linear program formulation are available for (P1), they are not appropriate anymore to tackle (P2) and (P3). Various methods are proposed for the TAP: a descent local search, a tabu search, and a learning tabu search (LTS). The latter is a new type of local search algorithm. It involves a learning process relying on a trail system, and it can be applied to any combinatorial optimization problem. Results are reported and discussed for a large set of instances (for (P1), (P2), and (P3)), and show the good performance of LTS.

Keywords

  • Truck allocation problem
  • Metaheuristics
  • Tabu search

Citation (ISO format)

SCHINDL, David, ZUFFEREY, Nicolas. A learning tabu search for a truck allocation problem with linear and nonlinear cost components. In: Naval Research Logistics (NRL), 2015, vol. 62, n° 1, p. 32–45. doi: 10.1002/nav.21612

Main files (1)

Article (Published version)

Identifiers

668views
0downloads

Technical informations

Creation

08/06/2015 19:37:00

First validation

08/06/2015 19:37:00

Update

14/03/2023 23:22:58

Status update

14/03/2023 23:22:58

Last indexation

31/10/2024 00:30:19
All rights reserved by Archive ouverte UNIGE and the University of Geneva
OpenAIRE Indexed & Validated