Adaptive Logit Models for Constructing Feasible Solution for the Dial-a-Ride Problem

This article proposes a method to construct feasible solutions for dial-a-ride problem. Dial-a-ride problem is a routing problem for a set of time-constrained travel requests using a limited number of capacity-constrained vehicles. Obtaining a feasible solution can help identifying an upper bound for the optimal solution and aid in creating a pool of solutions for heuristic methods. The proposed method uses a stepwise greedy approach to create the sequence of passengers’ pick-up/drop-off nodes for every available vehicle while minimising the likelihood of infeasibility. The sequence starts from vehicle’s depot and at every step a node on the vehicle route is selected. In multi-vehicle cases, the process is repeated for subsequent vehicles to serve the remaining passengers. Any remaining passengers after all routes are built are inserted in the constructed routes using an insertion method. The process of selecting nodes when constructing routes are dictated by three strategies, and the probability of success in constructing a feasible solution in continuing with each of the strategies is estimated using a binary logit model. The calibration process for the logit models is inspired by reinforcement learning. In this process, the parameters of the logit models are calibrated using a small-scale instance the size of which is gradually increased, and the model is re-calibrated when the performance of the model drops below a prespecified threshold. The efficiency and transferability of the proposed method in obtaining feasible solutions is examined using 100 random instances each with 50 requests and with varying levels of time constraints on a transport network represented using a directed graph. The performance of the method is compared with the well-established parallel insertion heuristic on a widely used benchmark series. The results show that the proposed method can return a feasible solution for all examined instances and is 2.8 times faster in initialisation, and it reduces the average optimisation run time by 4.18 percent