A multi-objective open vehicle routing problem with overbooking: Exact and heuristic solution approaches for an employee transportation problem

Erdi Dasdemir, Murat Caner Testik, Diclehan Tezcaner Öztürk, Ceren Tuncer Şakar, Güldal Güleryüz and Özlem Müge Testik

Omega, 2022, vol. 108, issue C

Abstract: We address a bus routing problem, where individuals need to be gathered from spatially distributed pickup points and transported to a workplace. The problem is modeled as an open vehicle routing problem. Overbooking is allowed because the total seat capacity of the buses is limited. The problem is treated as a multi-objective optimization problem, where the total distance traveled by the buses and the total number of straphangers in the buses are minimized. We develop a mixed integer programming (MIP) model and employ the ε-constraint method to generate the Pareto-optimal frontier. Due to the high computational requirements of the exact model, two heuristic approaches are developed: a heuristic algorithm that is based on a cluster-first and route-second algorithm and a multi-objective evolutionary algorithm. We also develop another MIP model that provides an alternative bound to evaluate the quality of the heuristics’ solutions. Experiments on a small and a moderate-sized problem show that the heuristics are fast and approximate the optimal solutions well. The heuristic approaches are then used to solve the actual problem having 103 pickup points, 50 buses and 1986 individuals. A set of approximate solutions whose total transportation distances are at most 14% worse than the best lower bounds are obtained.

Keywords: Open vehicle routing problem; Employee transportation; Overbooking; Multi-objective optimization; Mixed integer programming; Heuristics (search for similar items in EconPapers)
Date: 2022
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (6)

Downloads: (external link)
http://www.sciencedirect.com/science/article/pii/S0305048321001961
Full text for ScienceDirect subscribers only

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:eee:jomega:v:108:y:2022:i:c:s0305048321001961

Ordering information: This journal article can be ordered from
http://www.elsevier.com/wps/find/supportfaq.cws_home/regional
https://shop.elsevie ... _01_ooc_1&version=01

DOI: 10.1016/j.omega.2021.102587

Access Statistics for this article

Omega is currently edited by B. Lev

More articles in Omega from Elsevier
Bibliographic data for series maintained by Catherine Liu ().