Modelling and solving the split-delivery vehicle routing problem, considering loading constraints and spoilage of commodities

Abstract

In a typical supply chain, an aggregation hub is a strategically located facility that collects, processes and distributes commodities. This requires determining the collection/distribution fleet size, and the shortest routes to/from the served locations. Perishable commodities further require considering the order of collection/delivery and the loading positions inside the trucks. In this paper, the split-delivery vehicle routing problem (SDVRP) is modelled and solved, considering multiple perishable commodities, loading constraints, cross-docking and a heterogeneous fleet of trucks. The objective is to manage a fleet of trucks operating from an aggregation hub in order to minimise the total transportation and products spoilage costs. The problem is first formulated using as a novel mixed integer linear programming (MILP) model. Due to the complexity of the problem, a hybrid ant colony optimisation (ACO) algorithm is proposed to solve the problem. The ACO is embedded with local search (LS) techniques to improve its exploitation capabilities and convergence speed. Experiments are conducted to assess the performance of the ACO/LS algorithm in solving a number of benchmarked SDVRP instances. Results show that the proposed algorithm has an acceptable performance regarding the SDVRP, and can further handle all the aspects considered in the current problem efficiently.

KEYWORDS:

• Aggregation hubs
• split-delivery vehicle routing problem
• hybrid ant-colony optimisation
• loading constraints
• perishable commodities

Acknowledgment

This work is supported by the American University in Cairo (AUC), Egypt, under Research Support Grant number: SSE-MENG-S.F.-FY19-FY20-FY21-RG(2-18)-2018-Feb-10-19-10-45.

Disclosure statement

The authors report there are no competing interests to declare.

Data availability statement

The data that support the findings of this study are available in the SDVRPLIB library at https://www.uv.es/belengue/sdvrp.html (Belenguer et al., 2000), and at www.rhsmith.umd.edu/faculty/bgolden/index.html (Chen et al., 2007).

Additional information

Funding

This work was supported by The American University in Cairo (AUC) [grant number SSE-MENG-S.F.-FY19-FY20-FY21-RG(2-18)-2018-Feb-10-].

Notes on contributors

Sherif A. Fahmy

Sherif Fahmy is currently an Associate Professor at the American University in Cairo (AUC), Egypt. He received his B.Sc. and M.Sc. degrees from Cairo University, and his Ph.D. degree in Mechanical and Industrial engineering from the University of Manitoba, Winnipeg, in 2009. He has more than 20 years of academic experience, from Teaching Assistant to Associate Professor, in Egypt, Canada, and Kuwait. Dr. Fahmy also worked as a process manager in the area of healthcare improvement using lean and six sigma and various industrial engineering techniques. He also has extensive experience in innovation management, IP management, and technology transfer and commercialisation, as he had been managing the innovation programme in Egypt’s biggest fund for science and technology. He has been a member of many professional societies and a reviewer for a number of academic journals.

Mohamed L. Gaafar

Mohamed Gaafar received his B.Sc. degree in Mechanical Engineering from the American University in Cairo (AUC), Egypt. Since his graduation, he has followed a career in supply chain management, from Procurement Executive to currently a Supply Chain Associate in Amazon Egypt.