Search

Pairwise route synchronization constraints are commonly encountered in the field of service technician routing and scheduling and in the area of mobile care. Pairwise route synchronization refers to constraints that require that two technicians or home care workers visit the same location at exactly the same time. We consider constraints of this type in the context of the well-known vehicle routing problem with time windows and a generic service technician routing and scheduling problem. Different approaches for dealing with the problem of pairwise route synchronization are compared and several ways of integrating a synchronization component into a metaheuristic algorithm tailored to the original problems are analyzed. When applied to benchmark instances from the literature, our algorithm matches almost all available optimal values and it produces several new best results for the remaining instances. [ABSTRACT FROM AUTHOR]

The consistent vehicle routing problem (ConVRP) takes customer satisfaction into account by assigning one driver to a customer and by bounding the variation in the arrival times over a given planning horizon. These requirements may be too restrictive in some applications. In the generalized ConVRP (GenConVRP), each customer is visited by a limited number of drivers and the variation in the arrival times is penalized in the objective function. The vehicle departure times may be adjusted to obtain stable arrival times. Additionally, customers are associated with AM/PM time windows. In contrast to previous work on the ConVRP, we do not use the template concept to generate routing plans. Our approach is based on a flexible large neighborhood search that is applied to the entire solution. Several destroy and repair heuristics have been designed to remove customers from the routes and to reinsert them at better positions. Arrival time consistency is improved by a simple 2-opt operator that reverses parts of particular routes. A computational study is performed on ConVRP benchmark instances and on new instances generated for the generalized problem. The proposed algorithm performs well on different variants of the ConVRP. It outperforms template-based approaches in terms of travel cost and time consistency. For the GenConVRP, we experiment with different input parameters and examine the trade-off between travel cost and customer satisfaction. Remarkable cost savings can be obtained by allowing more than one driver per customer. [ABSTRACT FROM AUTHOR]

In this article, we study the school bus routing and scheduling problem with transfers arising in the field of nonperiodic public transportation systems. It deals with the transportation of pupils from home to their school in the morning taking the possibility that pupils may change buses into account. Allowing transfers has several consequences. On the one hand, it allows more flexibility in the bus network structure and can, therefore, help to reduce operating costs. On the other hand, transfers have an impact on the service level: the perceived service quality is lower due to the existence of transfers; however, at the same time, user ride times may be reduced and, thus, transfers may also have a positive impact on service quality. The main objective is the minimization of the total operating costs. We develop a heuristic solution framework to solve this problem and compare it with two solution concepts that do not consider transfers. The impact of transfers on the service level in terms of time loss (or user ride time) and the number of transfers is analyzed. Our results show that allowing transfers reduces total operating costs significantly while average and maximum user ride times are comparable to solutions without transfers. © 2015 Wiley Periodicals, Inc. NETWORKS, Vol. 65(2), 180-203 2015 [ABSTRACT FROM AUTHOR]

An increasing number of companies focus on customer satisfaction to increase the lifetime value of each customer. In vehicle routing, customer satisfaction is often a result of consistent service. Customers appreciate service at regular times of the day provided by the same driver each time. Additionally, drivers become more familiar with their tasks if they visit the same customers and service regions repeatedly. In this article, we survey literature that addresses service consistency in vehicle routing. We present early solution approaches, starting from the 1970s, that focus on reducing the operational complexity resulting from planning and executing new routes each day. One side benefit of these approaches is service consistency; therefore, many recent solution approaches devised for improving customer satisfaction are based on previous achievements. We classify the literature according to three consistency features: arrival time consistency, person-oriented consistency, and delivery consistency. For each feature, we survey different modeling concepts and measurements, demonstrate solution approaches, and examine the increase in cost of improving service consistency. We close the article by presenting challenging ideas for future research. © 2014 The Authors Networks Published by Wiley Periodicals, Inc. NETWORKS, Vol. 64(3), 192-213 2014 [ABSTRACT FROM AUTHOR]

The Electric Autonomous Dial-A-Ride Problem (E-ADARP) consists in scheduling a fleet of electric autonomous vehicles to provide ride-sharing services for customers that specify their origins and destinations. The E-ADARP considers the following perspectives: (i) a weighted-sum objective that minimizes both total travel time and total excess user ride time; (ii) the employment of electric autonomous vehicles and a partial recharging policy. This paper presents the first labeling algorithm for a path-based formulation of the DARP/E-ADARP, where the main ingredient includes: (1) fragment-based representation of paths, (2) a novel approach that abstracts fragments to arcs while ensuring excess-user-ride-time optimality, (3) construction of a sparser new graph with the abstracted arcs, which is proven to preserve all feasible routes of the original graph, and (4) strong dominance rules and constant-time feasibility checks to compute the shortest paths efficiently. This labeling algorithm is then integrated into Branch-and-Price (B&P) algorithms to solve the E-ADARP. In the computational experiments, the B&P algorithm achieves optimality in 71 out of 84 instances. Remarkably, among these instances, 50 were solved optimally at the root node without branching. We identify 26 new best solutions, improve 30 previously reported lower bounds, and provide 17 new lower bounds for large-scale instances with up to 8 vehicles and 96 requests. In total 42 new best solutions are generated on previously solved and unsolved instances. In addition, we analyze the impact of incorporating the total excess user ride time within the objectives and allowing unlimited visits to recharging stations. The following managerial insights are provided: (1) solving a weighted-sum objective function can significantly enhance the service quality, while still maintaining operational costs at nearly optimal levels, (2) the relaxation on charging visits allows us to solve all instances feasibly and further reduces the average solution cost. • We use a new paradigm to minimize (excess-)user-ride-time in the labeling algorithm. • Our CG algorithm optimizes 50 out of 84 instances at the root node. • Our CG algorithm obtains 24 better lower bounds than the best-reported results. • Our CG algorithm identifies 22 new best solutions and 15 new optimal solutions. • The B&P solves 71 out of 84 instances optimally and obtains 26 new best solutions. • The B&P obtains 30 better lower bounds compared to the best-reported results. • We investigate the impact of adding the total excess user ride time in the objectives. [ABSTRACT FROM AUTHOR]