Exact and meta-heuristic approach for a general heterogeneous dial-a-ride problem with multiple depots

Dial-a-ride problems are concerned with the design of efficient vehicle routes for transporting individual persons from specific origin to specific destination locations. In real-life this operational planning problem is often complicated by several factors. Users may have special requirements (e.g. to be transported in a wheelchair) while service providers operate a heterogeneous fleet of vehicles from multiple depots in their service area. In this paper, a general dial-a-ride problem in which these three real-life aspects may simultaneously be taken into account is introduced: the Multi-Depot Heterogeneous Dial-A-Ride Problem (MD-H-DARP). Both a three- and two-index formulation are discussed. A branch-and-cut algorithm for the standard dial-a-ride problem is adapted to exactly solve small problem instances of the MD-H-DARP. To be able to solve larger problem instances, a new deterministic annealing meta-heuristic is proposed. Extensive numerical experiments are presented on different sets of benchmark instances for the homogeneous and the heterogeneous single depot dial-a-ride problem. Instances for the MD-H-DARP are introduced as well. The branch-and-cut algorithm provides considerably better results than an existing algorithm which uses a less compact formulation. All seven previously unsolved benchmark instances for the heterogeneous dial-a-ride problem could be solved to optimality within a matter of seconds. While computation times of the exact algorithm increase drastically with problem size, the proposed meta-heuristic algorithm provides near-optimal solutions within limited computation time for all instances. Several best known solutions for unsolved instances are improved and the algorithm clearly outperforms current state-of-the-art heuristics for the homogeneous and heterogeneous dial-a-ride problem, both in terms of solution quality and computation time.     

The time-dependent vehicle routing problem with soft time windows and stochastic travel times

This paper studies a vehicle routing problem with time-dependent and stochastic travel times. In our problem setting, customers have soft time windows. A mathematical model is used in which both efficiency for service as well as reliability for customers are taken into account. Depending on whether service times are included or not, we consider two versions of this problem. Two metaheuristics are built: a Tabu Search and an Adaptive Large Neighborhood Search. We carry out our experiments for well-known problem instances and perform comprehensive analyses on the numerical results in terms of the computational time and the solution quality. Experiments confirm that the proposed procedure is effective to obtain very good solutions to be performed in real-life environment.     

A Bayesian approach to detect pedestrian destination-sequences from WiFi signatures

In this paper, we propose a methodology to use the communication network infrastructure, in particular WiFi traces, to detect the sequence of activity episodes visited by pedestrians. Due to the poor quality of WiFi localization, a probabilistic method is proposed that infers activity-episode locations based on WiFi traces and calculates the likelihood of observing these traces in the pedestrian network, taking into account prior knowledge. The output of the method consists of candidates of activity-episodes sequences associated with the likelihood to be the true one. The methodology is validated on traces generated by a known sequence of activities, while the performance being evaluated on a set of anonymous users. Results show that it is possible to predict the number of episodes and the activity-episodes locations and durations, by merging information about the activity locations on the map, WiFi measurements and prior information about schedules and the attractivity in pedestrian infrastructure. The ambiguity of each activity episode in the sequence is explicitly measured.     

Vehicle routing with roaming delivery locations

We propose the vehicle routing problem with roaming delivery locations (VRPRDL) to model an innovation in last-mile delivery where a customer’s order is delivered to the trunk of his car. We develop construction and improvement heuristics for the VRPRDL based on two problem-specific techniques: (1) efficiently optimizing the delivery locations for a fixed customer delivery sequence and (2) efficiently switching a predecessor’s or successor’s delivery location during the insertion or deletion of a customer in a route. Furthermore, we conduct an extensive computation study to assess and quantify the benefits of trunk delivery in a variety of settings. The study reveals that a significant reduction in total distance travelled can be achieved, especially when trunk delivery is combined with traditional home delivery, which has both economic and environmental benefits.     

An integrated modelling approach for the bicriterion vehicle routing and scheduling problem with environmental considerations

The consideration of pollution in routing decisions gives rise to a new routing framework where measures of the environmental implications are traded off with business performance measures. To address this type of routing decisions, we formulate and solve a bi-objective time, load and path-dependent vehicle routing problem with time windows (BTL-VRPTW). The proposed formulation incorporates a travel time model representing realistically time varying traffic conditions. A key feature of the problem under consideration is the need to address simultaneously routing and path finding decisions. To cope with the computational burden arising from this property of the problem we propose a network reduction approach. Computational tests on the effect of the network reduction approach on determining non-dominated solutions are reported. A generic solution framework is proposed to address the BTL-VRPTW. The proposed framework combines any technique that creates capacity-feasible routes with a routing and scheduling method that aims to convert the identified routes to problem solutions. We show that transforming a set of routes to BTL-VRPTW solutions is equivalent to solving a bi-objective time dependent shortest path problem on a specially structured graph. We propose a backward label setting technique to solve the emerging problem that takes advantage of the special structure of the graph. The proposed generic solution framework is implemented by integrating the routing and scheduling method into an Ant Colony System algorithm. The accuracy of the proposed algorithm was assessed on the basis of its capability to determine minimum travel time and fuel consumption solutions. Although the computational results are encouraging, there is ample room for future research in algorithmic advances on addressing the proposed problem.     

Dynamic traffic routing in a network with adaptive signal control

In real traffic networks, travellers’ route choice is affected by traffic control strategies. In this research, we capture the interaction between travellers’ route choice and traffic signal control in a coherent framework. For travellers’ route choice, a VANET (Vehicular Ad hoc NETwork) is considered, where travellers have access to the real-time traffic information through V2V/V2I (Vehicle to Vehicle/Vehicle to Infrastructure) infrastructures and make route choice decisions at each intersection using hyper-path trees. We test our algorithm and control strategy by simulation in OmNet++ (A network communication simulator) and SUMO (Simulation of Urban MObility) under several scenarios. The simulation results show that with the proposed dynamic routing, the overall travel cost significantly decreases. It is also shown that the proposed adaptive signal control reduces the average delay effectively, as well as reduces the fluctuation of the average speed within the whole network.     

Customized bus service design for jointly optimizing passenger-to-vehicle assignment and vehicle routing

Emerging transportation network services, such as customized buses, hold the promise of expanding overall traveler accessibility in congested metropolitan areas. A number of internet-based customized bus services have been planned and deployed for major origin-destination (OD) pairs to/from inner cities with limited physical road infrastructure. In this research, we aim to develop a joint optimization model for addressing a number of practical challenges for providing flexible public transportation services. First, how to maintain minimum loading rate requirements and increase the number of customers per bus for the bus operators to reach long-term profitability. Second, how to optimize detailed bus routing and timetabling plans to satisfy a wide range of specific user constraints, such as passengers’ pickup and delivery locations with preferred time windows, through flexible decision for matching passengers to bus routes. From a space-time network modeling perspective, this paper develops a multi-commodity network flow-based optimization model to formulate a customized bus service network design problem so as to optimize the utilization of the vehicle capacity while satisfying individual demand requests defined through space-time windows. We further develop a solution algorithm based on the Lagrangian decomposition for the primal problem and a space-time prism based method to reduce the solution search space. Case studies using both the illustrative and real-world large-scale transportation networks are conducted to demonstrate the effectiveness of the proposed algorithm and its sensitivity under different practical operating conditions.     

Time-dependent green vehicle routing problem with stochastic vehicle speeds: An approximate dynamic programming algorithm

This paper addresses a Time Dependent Capacitated Vehicle Routing Problem with stochastic vehicle speeds and environmental concerns. The problem has been formulated as a Markovian Decision Process. As distinct from the traditional attempts on the problem, while estimating the amount of fuel consumption and emissions, the model takes time-dependency and stochasticity of the vehicle speeds into account. The Time Dependent Capacitated Vehicle Routing Problem is known to be NP-Hard for even deterministic settings. Incorporating uncertainty to the problem increases complexity, which renders classical optimization methods infeasible. Therefore, we propose an Approximate Dynamic Programming based heuristic as a decision aid tool for the problem. The proposed Markovian Decision Model and Approximate Dynamic Programming based heuristic are flexible in terms that more environmentally friendly solutions can be obtained by changing the objective function from cost minimization to emissions minimization. The added values of the proposed decision support tools have been shown through computational analyses on several instances. The computational analyses show that incorporating vehicle speed stochasticity into decision support models has potential to improve the performance of resulting routes in terms of travel duration, emissions and travel cost. In addition, the proposed heuristic provides promising results within relatively short computation times.     

A tailored branch-and-price approach for a joint tramp ship routing and bunkering problem

This paper deals with a practical tramp ship routing problem while taking into account different bunker prices at different ports, which is called the joint tramp ship routing and bunkering (JSRB) problem. Given a set of cargoes to be transported and a set of ports with different bunker prices, the proposed problem determines how to route ships to carry the cargoes and the amount of bunker to purchase at each port, in order to maximize the total profit. After building an integer linear programming model for the JSRB problem, we propose a tailored branch-and-price (B&P) solution approach. The B&P approach incorporates an efficient method for obtaining the optimal bunkering policy and a novel dominance rule for detecting inefficient routing options. The B&P approach is tested with randomly generated large-scale instances derived from real-world planning problems. All of the instances can be solved efficiently. Moreover, the proposed approach for the JSRB problem outperforms the conventional sequential planning approach and can incorporate the prediction of future cargo demand to avoid making myopic decisions.     

Activity-based market equilibrium for capacitated multimodal transport systems

Empirical studies have shown that demand for multimodal transport systems is highly correlated with activity schedules of individuals. Nonetheless, existing analytical equilibrium models of multimodal systems have only considered trip-based demand. We propose a new market equilibrium model that is sensitive to traveler activity schedules and system capacities. The model is based on a constrained mixed logit model of activity schedule choice, where each schedule in the choice set is generated with a multimodal extension of the household activity pattern problem. The extension explicitly accounts for both passenger choices of activity participation and multimodal choices like public transit, walking, and vehicle parking. The market equilibrium is achieved with Lagrangian relaxation to determine the optimal dual price of the capacity constraint, and a method of successive averages with column generation finds an efficient choice set of activity schedules to assign flows over the dynamic network load capacities. An example illustrates the model and algorithm, effects similar to Vickrey’s morning commute model can be observed as a special case. A case study of the Oakville Go Transit station access “last mile” problem in the Greater Toronto Area is conducted with 166 survey samples reflecting 3680 individuals. Results suggest that a $10 fixed parking fee at Oakville station would lead to a reduction of access auto share from 54.8% to 49.5%, an increase in access transit share from 20.7% to 25.9%, and a disutility increase of 11% for the of single-activity residents of Oakville.