Solving the Fleet Size and Mix Vehicle Routing Problem with Time Windows via Adaptive Memory Programming

This paper presents a novel Adaptive Memory Programming (AMP) solution approach for the Fleet Size and Mix Vehicle Routing Problem with Time Windows (FSMVRPTW). The FSMVRPTW seeks to design a set of depot returning vehicle routes to service a set of customers with known demands, for a heterogeneous fleet of vehicles with different capacities and fixed costs. Each customer is serviced only once by exactly one vehicle, within fixed time intervals that represent the earliest and latest times during the day that service can take place. The objective is to minimize the total transportation costs, or similarly to determine the optimal fleet composition and dimension following least cost vehicle routes. The proposed method utilizes the basic concept of an AMP solution framework equipped with a probabilistic semi-parallel construction heuristic, a novel solution re-construction mechanism, an innovative Iterated Tabu Search algorithm tuned for intensification local search and frequency-based long term memory structures. Computational experiments on well-known benchmark data sets illustrate the efficiency and effectiveness of the proposed method. Compared to the current state-of-the-art, the proposed method improves the best reported cumulative and mean results over most problem instances with reasonable computational requirements.     

A decomposition-based iterative optimization algorithm for traveling salesman problem with drone

This study investigates a new delivery problem that has emerged after the attempts of several e-commerce and logistics firms to deploy drones in their operations to increase efficiency and reduce delivery times. In this problem, a delivery truck that carries a drone on its roof serves customers in coordination with a drone. The drone is considered to complement the truck due to its cost-efficiency and ability to access difficult terrains and to travel without exposure to congestion. This study presents an iterative algorithm that is based on a decomposition approach to minimize delivery completion time. In the first stage of the proposed methodology, the truck route and the customers assigned to the drone are determined. In the second stage, a mixed-integer linear programming model is solved to optimize the drone route by fixing the routing and the assignment decisions that are made in the first stage. Beginning with the shortest truck route, the assignment and the routing decisions are iteratively improved. The solution times of our algorithm are compared with the solution times of the state-of-the-art formulations that are solved by CPLEX. The results demonstrate that our algorithm yields shorter solution times for the instances that we generated with the specified parameters. An optimization-based heuristic algorithm, which obtains solutions for medium-sized instances, is developed by reducing the feasible search area.     

A model for estimating the optimal cycle length of demand responsive feeder transit services

The general lack of first/last mile connectivity is one of the main challenges faced by today’s public transit. One of the possible actions towards a solution to this problem is the planning, design and implementation of efficient feeder transit services. This paper develops an analytical model which allows for an easy computation of near optimal terminal-to-terminal cycle length of a demand responsive feeder service to maximize service quality provided to customers, defined as the inverse of a weighted sum of waiting and riding times. The model estimates the recommended cycle length by only plugging in geometrical parameters and demand data, without relying on extensive simulation analyses or rule of thumbs. Simulation experiments and comparisons with real services validate our model, which would allow planners, decision makers and practitioners to quickly identify the best feeder transit operating design of any given residential area.     

Optimal scheduling of a taxi fleet with mixed electric and gasoline vehicles to service advance reservations

This study addresses the problem of scheduling a fleet of taxis that are appointed to solely service customers with advance reservations. In contrast to previous studies that have dealt with the planning and operations of a taxi fleet with only electric vehicles (EVs), we consider that most taxi companies may have to operate with fleets comprised of both gasoline vehicles (GVs) and plug-in EVs during the transition from GV to (complete) EV taxi fleets. This paper presents an innovative multi-layer taxi-flow time-space network which effectively describes the movements of the taxis in the dimensions of space and time. An optimization model is then developed based on the time-space network to determine an optimal schedule for the taxi fleet. The objective is to minimize the total operating cost of the fleet, with a set of operating constraints for the EVs and GVs included in the model. Given that the model is formulated as an integer multi-commodity network flow problem, which is characterized as NP-hard, we propose two simple but effective decomposition-based heuristics to efficiently solve the problem with practical sizes. Test instances generated based on the data provided by a Taiwan taxi company are solved to evaluate the solution algorithms. The results show that the gaps between the objective values of the heuristic solutions and those of the optimal solutions are less than 3%, and the heuristics require much less time to obtain the good quality solutions. As a result, it is shown that the model, coupled with the algorithms, can be an effective planning tool to assist the company in routing and scheduling its fleet to service reservation customers.     

A differential evolution approach for the vehicle routing problem with backhauls and time windows

This paper presents a differential evolution algorithm (DEA) to solve a vehicle routing problem with backhauls and time windows (VRPBTW) and applied for a catering firm. VRPBTW is an extension of the vehicle routing problem, which includes capacity and time window constraints. In this problem, customers are divided into two subsets: linehaul and backhaul. Each vehicle starts from a depot and goods are delivered from the depot to the linehaul customers. Goods are subsequently brought back to the depot from the backhaul customers. The objective is to minimize the total distance that satisfies all of the constraints. The problem is formulated using mixed integer programming and solved using DEA. Proposed algorithm is tested with several benchmark problems to demonstrate effectiveness and efficiency of the algorithm and results show that our proposed algorithm can find superior solutions for most of the problems in comparison with the best known solutions. Hence, DEA was carried out for catering firm to minimize total transportation costs. Copyright © 2013 John Wiley & Sons, Ltd.     

Check-in allocation improvements through the use of a simulation–optimization approach

The aeronautical industry is still under expansion in spite of the problems it is facing due to the increase in oil prices, limited capacity, and novel regulations. The expansion trends translate into problems at different locations within an airport system and are more evident when the resources to cope with the demand are limited or are reaching to theirs limits. In the check-in areas they are appreciated as excessive waiting times which in turn are appreciated by the customers as bad service levels. The article presents a novel methodology that combines an evolutionary algorithm and simulation in order to give the best results taking into account not only the mandatory hard and soft rules determined by the internal policies of an airport terminal but also the quality indicators which are very difficult to include using an abstract representation. The evolutionary algorithm is developed to satisfy the different mandatory restrictions for the allocation problem such as minimum and maximum number of check-in desks per flight, load balance in the check-in islands, opening times of check-in desks and other restrictions imposed by the level of service agreement. Once the solutions are obtained, a second evaluation is performed using a simulation model of the terminal that takes into account the stochastic aspects of the problem such as arriving profiles of the passengers, opening times physical configurations of the facility among other with the objective to determine which allocation is the most efficient in real situations in order to maintain the quality indicators at the desired level.     

Customers’ selections between premium electric taxis and liquefied petroleum gas taxis

Reducing roadside emissions is a common challenge in metropolitan cities. In Hong Kong, conventional liquefied petroleum gas taxis are one of the main contributors to roadside emissions as they operate on the streets 24 h a day with a long daily driving mileage. Moreover, these taxis suffer from a severely poor service reputation. To enhance the environmental friendliness and service quality of the taxi industry, this study explores the market potential of operating premium electric taxis in the dispatching mode. A stated preference survey was conducted to 1410 taxi customers about their taxi-riding choices between premium electric taxis and conventional liquefied petroleum gas taxis. In total, 5640 observations were obtained and used to develop a series of binary logistic regression models with different model formulations for the determination of the significant factors influencing customers’ selections. The findings indicate that walk time to and wait time for taxis were the most critical concerns to the customers, and they were more willing to take premium taxis if their journey distance was longer and their desired improvement on taxi service quality was greater. The socio-demographic status of taxi customers also influences their choices. The associated policy implications are discussed for promoting taxis with better service quality and fewer roadside emissions. The findings provide some policy insights to other international cities that have a similar taxi market to Hong Kong.     

Scheduling railway freight delivery appointments using a bid price approach

This paper proposes a method for establishing aggressive but achievable delivery appointment times for railroad shipments, taking into account individual customer needs and forecasted available train capacity. The concept of scheduling appointment times is directly patterned after current motor carrier industry practice, so that customers can plan for rail or truck deliveries in the same way.A shipment routing problem is decomposed into a deterministic “dynamic car scheduling” (DCS) process for shipments already accepted and a stochastic “train segment pricing” (TSP) process for forecasting future demands which have not yet called in and for which delivery appointments have yet to be scheduled. Both are formulated as multi-commodity network flow (MCNF) problems, where each shipment is treated as a separate commodity. Gain coefficients represent recapture probabilities that a specific customer will accept a carrier’s service offer.A comparison with a widely used revenue management formulation is given. A Lagrangian heuristic for obtaining a primal solution is also described. The problem is solved within a 1% gap using the subgradient algorithm.     

Nonlinear pricing for stochastic container leasing system

With the substantial upsurge of container traffic, the container leasing company thrives on the financial benefits and operational flexibility of leasing containers requested by shippers. In practice, container lease pricing problem is different from the consumer product pricing in consideration of the fair value of container, limited customer types and monopolistic supply market. In view of the durability of container and the diversified lease time and quantity, the pricing is a challenging task for the leasing company. This paper examines the monopolist’s nonlinear pricing problems in static and dynamic environments. In particular, the leasing company designs and commits a menu of price and hire quantity/time pairs to maximize the expected profit and in turn customers choose hire quantities/time to maximize their surpluses according to their hire preferences. In a static environment, closed-form solutions are obtained for different groups of customers with multiple types subject to capacity constraint. In a dynamic environment, we address two customer types and derive closed-form solutions for the problem of customers with hire time preference. Further, we show that the effect of the capacity constraint increases with time of the planning horizon when customers have the same hire time preference; while in the case with different hire time preferences, the capacity constraint has opposite effects on the low and high type customers. Last, the case of customers with hire quantity preference is discussed. We focus on the lease with alternative given sets of hire time and use dynamic programming to derive the numerical optimal hire time sequence.     

A Granular Variable Tabu Neighborhood Search for the capacitated location-routing problem

This paper proposes a new heuristic algorithm for the Capacitated Location-Routing Problem (CLRP), called Granular Variable Tabu Neighborhood Search (GVTNS). This heuristic includes a Granular Tabu Search within a Variable Neighborhood Search algorithm. The proposed algorithm is experimentally compared on the benchmark instances from the literature with several of the most effective heuristics proposed for the solution of the CLRP, by taking into account the CPU time and the quality of the solutions obtained. The computational results show that GVTNS is able to obtain good average solutions in short CPU times, and to improve five best known solutions from the literature. The main contribution of this paper is to show a successful new heuristic for the CLRP, combining two known heuristic approaches to improve the global performance of the proposed algorithm for what concerns both the quality of the solutions and the computing times required to find them.     

Joint inventory-location problem under the risk of probabilistic facility disruptions

This paper studies a reliable joint inventory-location problem that optimizes facility locations, customer allocations, and inventory management decisions when facilities are subject to disruption risks (e.g., due to natural or man-made hazards). When a facility fails, its customers may be reassigned to other operational facilities in order to avoid the high penalty costs associated with losing service. We propose an integer programming model that minimizes the sum of facility construction costs, expected inventory holding costs and expected customer costs under normal and failure scenarios. We develop a Lagrangian relaxation solution framework for this problem, including a polynomial-time exact algorithm for the relaxed nonlinear subproblems. Numerical experiment results show that this proposed model is capable of providing a near-optimum solution within a short computation time. Managerial insights on the optimal facility deployment, inventory control strategies, and the corresponding cost constitutions are drawn.     

Modeling techniques for periodic vehicle routing problems

This paper presents a continuous approximation model for the period vehicle routing problem with service choice (PVRP-SC). The PVRP-SC is a variant of the period vehicle routing problem in which the visit frequency to nodes is a decision of the model. This variation can result in more efficient vehicle tours and/or greater service benefit to customers. We present a continuous approximation model to facilitate strategic and tactical planning of periodic distribution systems and evaluate the value of service choice. Further, results from the continuous model can provide guidelines for constructing solutions to the discrete PVRP-SC.     

The Hybrid Vehicle Routing Problem

In this paper the Hybrid Vehicle Routing Problem (HVRP) is introduced and formalized. This problem is an extension of the classical VRP in which vehicles can work both electrically and with traditional fuel. The vehicle may change propulsion mode at any point of time. The unitary travel cost is much lower for distances covered in the electric mode. An electric battery has a limited capacity and may be recharged at a recharging station (RS). A limited number of RS are available. Once a battery has been completely discharged, the vehicle automatically shifts to traditional fuel propulsion mode. Furthermore, a maximum route duration is imposed according to contracts regulations established with the driver. In this paper, a Mixed Integer Linear Programming formulation is presented and a Large Neighborhood Search based Matheuristic is proposed. The algorithm starts from a feasible solution and consists into destroying, at each iteration, a small number of routes, letting unvaried the other ones, and reconstructing a new feasible solution running the model on only the subset of customers involved in the destroyed routes. This procedure allows to completely explore a large neighborhood within very short computational time. Computational tests that show the performance of the matheuristic are presented. The method has also been tested on a simplified version of the HVRP already presented in the literature, the Green Vehicle Routing Problem (GVRP), and competitive results have been obtained.     

A set-covering model for a bidirectional multi-shift full truckload vehicle routing problem

This paper introduces a bidirectional multi-shift full truckload transportation problem with operation dependent service times. The problem is different from the previous container transport problems and the existing approaches for container transport problems and vehicle routing pickup and delivery are either not suitable or inefficient. In this paper, a set covering model is developed for the problem based on a novel route representation and a container-flow mapping. It was demonstrated that the model can be applied to solve real-life, medium sized instances of the container transport problem at a large international port. A lower bound of the problem is also obtained by relaxing the time window constraints to the nearest shifts and transforming the problem into a service network design problem. Implications and managerial insights of the results by the lower bound results are also provided.     

Signalized intersections with variable flow rates: II A model for delay estimation

This second part of our work develops a model for delay estimation at intersections whose traffic signal controls are continuously being updated. Generally, these traffic signals are centrally controlled. The foundation for the delay estimation model is based on a queuing theory model called “Preemptive resume discipline for M/G/1 with two priority levels.” This queuing model assumes that two customers arrive at acertain point by a Poisson arrival process, and that one customer has service priority over the second customer. The analogy for the case of intersection control is that the preferred customers are the red lights and the secondary customers are the vehicles. In order to adapt the model to the realistic behavior of vehicle traffic at continuously adjusted signals, components are derived to modify the model. The simulation results of the first part of this work are used to calculate adjustment factors that fairly accurately reproduce the simulated delays. This gives rise to the advantage of using in practice a closed mathematical model, in particular when trying to optimize the operation of signalized intersections at the network level.     

Research contributions to managing transit service reliability

Service reliability problems are a major concern shared by transit system users and operators. Unreliable service leads to additional vehicle requirements and higher operating costs; passengers suffer increased wait time and higher travel time uncertainty, leading to a general dissatisfaction with service and the possibility of seeking other means of transport. Because of the significance of this problem, considerable research attention has been focused in recent years on developing ways to improve service reliability. This paper examines contributions which have been made to managing transit service reliability. This topic encompasses the subjects of vehicle run time, run time variation, headway variation, passenger wait time, and reliability control. Both theoretical and empirical approaches have been undertaken, and each has contributed to our knowledge in addressing the overall problem. Significant contributions to the state-of-the-art are reported and the implications on present practice are discussed.     

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.     

Optimization of a feeder-bus route design by using a multiobjective programming approach

This paper presents a feeder-bus route design model, capable of minimizing route length, minimizing maximum route travel time of planned routes, and maximizing service coverage for trip generation. The proposed model considers constraints of route connectivity, subtour prevention, travel time upper bound of a route, relationships between route layout and service coverage, and value ranges of decision variables. Parameter uncertainties are dealt with using fuzzy numbers, and the model is developed as a multiobjective programming problem. A case study of a metro station in Taichung City, Taiwan is then conducted. Next, the programming problem in the case study is solved, based on the technique for order preference by similarity to ideal solution approach to obtain the compromise route design. Results of the case study confirm that the routes of the proposed model perform better than existing routes in terms of network length and service coverage. Additionally, increasing the number of feeder-bus routes decreases maximum route travel time, increases service coverage, and increases network length. To our knowledge, the proposed model is the first bus route design model in the literature to consider simultaneously various stakeholder needs and support for bus route planners in developing alternatives for further evaluation efficiently and systematically.     

Finding time‐robust fuel‐efficient paths for a call‐taxi in a stochastic city road network

Intra‐city commuting is being revolutionized by call‐taxi services in many developing countries such as India. A customer requests a taxi via phone, and it arrives at the right time and at the right location for the pick‐up. This mode of intra‐city travel has become one of the most reliable and convenient modes of transportation for customers traveling for business and non‐business purposes. The increased number of vehicles on city roads and raising fuel costs has prompted a new type of transportation logistics problem of finding a fuel‐efficient and quickest path for a call‐taxi through a city road network, where the travel times are stochastic. The stochastic travel time of the road network is induced by obstacles such as the traffic signals and intersections. The delay and additional fuel consumption at each of these obstacles are calculated that are later imputed to the total travel time and fuel consumption of a path. A Monte‐Carlo simulation‐based approach is proposed to identify unique fuel‐efficient paths between two locations in a city road network where each obstacle has a delay distribution. A multi‐criteria score is then assigned to each unique path based on the probability that the path is fuel efficient, the average travel time of the path and the coefficient of variation of the travel times of the path. Copyright © 2016 John Wiley & Sons, Ltd.     

Partial recharge strategies for the electric vehicle routing problem with time windows

The Electric Vehicle Routing Problem with Time Windows (EVRPTW) is an extension to the well-known Vehicle Routing Problem with Time Windows (VRPTW) where the fleet consists of electric vehicles (EVs). Since EVs have limited driving range due to their battery capacities they may need to visit recharging stations while servicing the customers along their route. The recharging may take place at any battery level and after the recharging the battery is assumed to be full. In this paper, we relax the full recharge restriction and allow partial recharging (EVRPTW-PR), which is more practical in the real world due to shorter recharging duration. We formulate this problem as a 0–1 mixed integer linear program and develop an Adaptive Large Neighborhood Search (ALNS) algorithm to solve it efficiently. We apply several removal and insertion mechanisms by selecting them dynamically and adaptively based on their past performances, including new mechanisms specifically designed for EVRPTW and EVRPTW-PR. These new mechanisms include the removal of the stations independently or along with the preceding or succeeding customers and the insertion of the stations with determining the charge amount based on the recharging decisions. We test the performance of ALNS by using benchmark instances from the recent literature. The computational results show that the proposed method is effective in finding high quality solutions and the partial recharging option may significantly improve the routing decisions.