EURO 2024 Copenhagen
Abstract Submission

EURO-Online login

1947. Ruin-and-recreate heuristics for the fixed charge transportation problem

Invited abstract in session TA-55: ML & OR Applications in Transport Modelling, stream Transportation.

Tuesday, 8:30-10:00
Room: S02 (building: 101)

Authors (first author is the speaker)

1. Gavin Le Roux
Department of Logistics, Stellenbosch University
2. Stephan Visagie
Department of Logistics, University of Stellenbosch

Abstract

Recently, the literature has become too focused on variations of the fixed charge transportation problem (FCTP), such as solid, step, capacitated or multi-stage, despite a significant number of gaps remaining in the research for pure FCTPs. The research presented is focused on developing ruin-and-recreate (R&R) heuristics specifically for pure FCTPs, which have not been implemented before. R&R heuristics are new methods applied to combinatorial optimisation problems (specifically vehicle routing problems) in which a solution is destructed (possibly reaching an infeasible solution) and rebuilt in an intelligent manner to maintain feasibility. This is done repeatedly until a desired solution is reached.

Four ruin methods utilising the tree structure of FCTP basic feasible solutions, seven recreate methods divided into single-cell and multi-cell heuristics, and various metrics to determine entering and leaving variables in each iteration of a ruin or recreate method, are developed. Different variations of the algorithms are executed on a set of existing and newly generated benchmarks for algorithmic comparisons. Different characteristics of a problem, such as the problem size, fixed charge to variable cost ratio, average units supplied/demanded and arc density, are reported on to determine strong performing algorithms in given situations. Lastly, the convergence of the algorithms as well as the trade-off between solution quality and computational time are explored.

Keywords

Status: accepted

Back to the list of papers