Hybrid metaheuristic for the dial-a-ride problem with private fleet and common carrier integrated with public transportation

Dial-a-ride operations consist of door-to-door transportation systems designed for users with specific needs. Governments and companies offer such services, and due to the flexibility and service level required by the users, it is considerably more costly than public transportation, besides emitting higher levels of CO2\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$_2$$\end{document}. Hence, it is crucial to analyze alternatives to improve operational costs and efficiency without compromising the quality of the service. This paper introduces a variant for the dial-a-ride problem with private fleets and common carriers (DARP-PFCC) integrated with public transportation. Requests can be served by the private fleet, the common carrier, or by integrating them into the public transportation system. In this case, users are collected at the pickup locations and taken to bus stops. After the bus trip, other vehicles serve them from the bus stops to their final destination. Bus schedules must be considered when deciding on the best integration trip. As a methodology, we solve this extension of the DARP-PFCC with a metaheuristic and machine learning hybrid method by combining a biased random key genetic algorithm with the Q-Learning and local search heuristics (BRKGA-QL). This paper also introduces some improvements to this method, particularly with respect to population quality and diversity, thanks to a new mutation method in the classical crossover operator and deterministic rules for the learning process. Computational experiments on a new benchmark data set with realistic data from Qu & eacute;bec City show that our BRKGA-QL outperforms its previous version. In addition, we provide a qualitative analysis for the DARP-PFCC, showing that the middle mile integration with public transportation can save up to 20% in operating costs, besides reducing the traveled distances of private vehicles and common carriers.