Variable fixing heuristics for the capacitated multicommodity network flow problem with multiple transport lines, a heterogeneous fleet and time windows

ABSTRACT

In this paper, we investigate a new variant of the multi-commodity network flow problem, taking into consideration multiple transport lines and time windows. This variant arises in a city logistics environment, more specifically in a long-haul passenger transport system that is also used to transport urban freight. We propose two mixed integer programming models for two objective functions: minimization of network operational costs and minimization of travel times. Since the problems under study are NP-hard, we propose three size reduction heuristics. In order to assess the performance of the proposed algorithms, we carried out computational experiments on a set of synthetic problem instances. We use the relative percentage deviation as performance criterion. For the cost objective function, a LP-and-Fix algorithm outperforms other methods in most tested instances, but for the travel time, a hybrid method (size reduction with LP-and-Fix algorithm) is, in general, better than other approaches.

KEYWORDS:

• Combinatorial optimization
• network design problems
• mixed integer linear programming
• city logistics
• size reduction algorithms

Disclosure statement

No potential conflict of interest was reported by the authors.

Additional information

Funding

This work was partially financed by the ERDF - European Regional Development Fund through the Operational Programme for Competitiveness and Internationalisation - COMPETE 2020 Programme and by National Funds through the Portuguese funding agency, FCT - Fundacção para a Ciência e a Tecnologia within project POCI-01-0145-FEDER-032053 and National Council for Scientific and Technological Development (CNPq) through grants [404232/2016-7 and 303594/2018-7].”