Hybrid column generation and large neighborhood search for the dial-a-ride problem

Demographic change towards an ever aging population entails an increasing demand for specialized transportation systems to complement the traditional public means of transportation. Typically, users place transportation requests, specifying a pickup and a drop off location and a fleet of minibuses or taxis is used to serve these requests. The underlying optimization problem can be modeled as a dial-a-ride problem. In the dial-a-ride problem considered in this paper, total routing costs are minimized while respecting time window, maximum user ride time, maximum route duration, and vehicle capacity restrictions. We propose a hybrid column generation and large neighborhood search algorithm and compare different hybridization strategies on a set of benchmark instances from the literature.     

A variable neighborhood search algorithm for the optimization of a dial-a-ride problem in a large city

On-demand transportation is becoming a new necessary service for modern (public and private) mobility and logistics providers. Large cities are demanding more and more share transportation services with flexible routes, resulting from user dynamic demands. In this study a new algorithm is proposed for solving the problem of computing the best routes that a public transportation company could offer to satisfy a number of customer requests. In this problem, known in the literature as the dial-a-ride problem, a number of passengers has to be transported between pickup and delivery locations trying to minimize the routing costs while respecting a set of pre-specified constraints (maximum pickup time, maximum ride duration and maximum load per vehicle). For optimizing this problem, a new variable neighborhood search has been developed and tested on a set of 24 different scenarios of a large-scale dial-a-ride problem in the city of San Francisco. The results have been compared against two state-of-the-art algorithms of the literature and validated by means of statistical procedures proving that the new algorithm has obtained the best overall results.     

Optimizing truck sequencing and truck dock assignment in a cross docking system

Cross docking plays a very importation role in supply chain management. The efficiency of cross docking will influence the lead time, inventory level and response time to the customer. This research aims to improve the efficiency of multi-door cross docking by optimizing both inbound and outbound truck sequencing and both inbound and outbound truck dock assignment. The objective is to minimize the makespan. The problem is new in the literature and no previous formulation of the problem can be found. In order to optimize the problem, a model for calculating the makespan is proposed. When given a sequence of all inbound and outbound trucks, the calculation model can assign all inbound and outbound trucks to all inbound and outbound doors based on first come first served and then calculate the makespan. The proposed makespan calculation model is then integrated with a variable neighborhood search (VNS) which can optimize the sequence of all inbound and outbound trucks. Four simulated Annealing (SA) algorithms are adopted for comparison. The experimental results show the proposed VNS provides 8.23–40.97% improvement over the solution generated randomly. Although it does not provide the best result for all problems when compared with SA algorithms, it provides robust results within a reasonable time. Thus the proposed method is efficient and effective in solving cross docking operation problems.     

A GRASP with adaptive large neighborhood search for pickup and delivery problems with transshipment

The pickup and delivery problem (PDP) has been studied extensively for applications ranging from courier, cargo and postal services, to public transportation. The work presented here was inspired by a daily route planning problem at a regional air carrier who was trying to determine the benefits of transshipment. Accordingly, a primary goal of this paper is identify the circumstances under which measurable cost saving can be achieved when one aircraft transports a request from its origin to an intermediate point and a second aircraft picks it up and delivers it to its final destination. In structuring the analysis, we describe a unique way to model this transshipment option on a directed graph and introduce a specialized two-route insertion heuristic that considers when to exploit this option. Based on the new representation, most existing heuristics for the PDP can be readily extended to handle transshipments.To find solutions, we developed a greedy randomized adaptive search procedure (GRASP) with several novel features. In the construction phase, shipment requests are inserted into routes until all demand is satisfied or no feasible insertion exists. In the improvement phase, an adaptive large neighborhood search algorithm is used to modify portions of the feasible routes. Specialized removal and insertion heuristics were designed for this purpose. In the absence of test cases in the literature, we also developed a procedure for randomly generating problem instances. Testing was done on 56 existing PDP instances which have 50 requests each, and on 50 new data sets with 25 requests each and one transshipment location. For the former, the performance and solution quality of the GRASP were comparable to the best known heuristics. For the latter, GRASP found the solutions within 1% of optimality on 88% of the instances.     

The Dial-A-Ride Problem with Transfers

The Dial-A-Ride Problem with Transfers (DARPT) consists in defining a set of routes that satisfy transportation requests of users between a set of pickup points and a set of delivery points, in the presence of ride time constraints. Users may change vehicles during their trip. This change of vehicle, called a transfer, is made at specific locations called transfer points. Solving the DARPT involves modeling and algorithmic difficulties. In this paper we provide a solution method based on an Adaptive Large Neighborhood Search (ALNS) metaheuristic and explain how to check the feasibility of a request insertion. The method is evaluated on real-life and generated instances. Experiments show that savings due to transfers can be up to 8% on real-life instances.     

Variable neighborhood search based approaches to a vehicle scheduling problem in agriculture

A vehicle scheduling problem (VSP) that arises from sugar beet transportation within minimum working time under the set of constraints reflecting a real‐life situation is considered. A mixed integer quadratically constrained programming (MIQCP) model of the considered VSP and reformulation to a mixed integer linear program (MILP) are proposed and used within the framework of Lingo 17 solver, producing optimal solutions only for small‐sized problem instances. Two variants of the variable neighborhood search (VNS) metaheuristic—basic VNS (BVNS) and skewed VNS (SVNS) are designed to efficiently deal with large‐sized problem instances. The proposed VNS approaches are evaluated and compared against Lingo 17 and each other on the set of real‐life and generated problem instances. Computational results show that both BVNS and SVNS reach all known optimal solutions on small‐sized instances and are comparable on medium‐ and large‐sized instances. In general, SVNS significantly outperforms BVNS in terms of running times.     

Generalized mixed integer and VNS heuristic approach to solving the multisize containers drayage problem

This paper addresses the problem of vehicle routing in drayage operations, where vehicles can carry containers of different sizes. The multisize container drayage problem with time windows is modeled as a multiple matching problem and formulated as a mixed integer linear program (MILP) model. The proposed MILP model determines optimal pickup and delivery routes of vehicles and is applicable to any type of vehicles capable of simultaneously transporting any arbitrary number of 20‐ and 40‐ft containers. To solve larger sized problems, we proposed a variable neighborhood search (VNS) heuristic. Both MILP and VNS approaches have been tested on numerous test instances and their performances are reported.     

A variable neighborhood search for the multi-depot vehicle routing problem with loading cost

The purpose of this paper is to propose a variable neighbourhood search (VNS) for solving the multi-depot vehicle routing problem with loading cost (MDVRPLC). The MDVRPLC is the combination of multi-depot vehicle routing problem (MDVRP) and vehicle routing problem with loading cost (VRPLC) which are both variations of the vehicle routing problem (VRP) and occur only rarely in the literature. In fact, an extensive literature search failed to find any literature related specifically to the MDVRPLC. The proposed VNS comprises three phases. First, a stochastic method is used for initial solution generation. Second, four operators are randomly selected to search neighbourhood solutions. Third, a criterion similar to simulated annealing (SA) is used for neighbourhood solution acceptance. The proposed VNS has been test on 23 MDVRP benchmark problems. The experimental results show that the proposed method provides an average 23.77% improvement in total transportation cost over the best known results based on minimizing transportation distance. The results show that the proposed method is efficient and effective in solving problems.     

Variable neighborhood search for location routing

In this paper we propose various neighborhood search heuristics (VNS) for solving the location routing problem with multiple capacitated depots and one uncapacitated vehicle per depot. The objective is to find depot locations and to design least cost routes for vehicles. We integrate a variable neighborhood descent as the local search in the general variable neighborhood heuristic framework to solve this problem. We propose five neighborhood structures which are either of routing or location type and use them in both shaking and local search steps. The proposed three VNS methods are tested on benchmark instances and successfully compared with other two state-of-the-art heuristics.     

A comparative study between dynamic adapted PSO and VNS for the vehicle routing problem with dynamic requests

Combinatorial optimization problems are usually modeled in a static fashion. In this kind of problems, all data are known in advance, i.e. before the optimization process has started. However, in practice, many problems are dynamic, and change while the optimization is in progress. For example, in the dynamic vehicle routing problem (DVRP), new orders arrive when the working day plan is in progress. In this case, routes must be reconfigured dynamically while executing the current simulation. The DVRP is an extension of a conventional routing problem, its main interest being the connection to many real word applications (repair services, courier mail services, dial-a-ride services, etc.). In this article, a DVRP is examined, and solving methods based on particle swarm optimization and variable neighborhood search paradigms are proposed. The performance of both approaches is evaluated using a new set of benchmarks that we introduce here as well as existing benchmarks in the literature. Finally, we measure the behavior of both methods in terms of dynamic adaptation.     

Variable neighborhood search for two-agent flow shop scheduling problem

Multi-agent scheduling in flow shop environment is seldom considered. In this paper flow shop scheduling problem with two agents is studied and its feasibility model is considered, in which the goal is to minimize the makespan of the first agent and the total tardiness of the second agent simultaneously under the given upper bounds. A simple variable neighborhood search (VNS) algorithm is proposed, in which a learning neighborhood structure is constructed to produce new solutions and a new principle is applied to decide if the current solution can be replaced with the new one. VNS is tested on a number of instances and the computational results show the promising advantage of VNS when compared to other algorithms of the problem.     

A decision support system for the bimodal dial-a-ride problem

A bimodal dial-a-ride problem (BDARP) considered in this paper is a dial-a-ride problem that involves two transportation modes: paratransit vehicles and fixed route buses. Riders in such a system might be transferred between different transportation modes during the service process. The motivation of this research is that by efficiently coordinating paratransit vehicles with fixed route buses we can improve the accessibility and efficiency of a dial-a-ride system. In this paper, we design a decision support system (DSS) which automatically constructs efficient paratransit vehicle routes and schedules for the BDARP. This DSS has been tested using actual data from the Ann Arbor Transportation Authority (AATA) in Ann Arbor, MI. The results show that this DSS produces an average increase of 10% in the number of requests that can be accommodated and an average decrease of 10% in the number of paratransit vehicles required, as compared to the manual results where no fixed route buses are involved     

An integration of mixed VND and VNS: the case of the multivehicle covering tour problem

The multivehicle covering tour problem (m‐CTP) is a transportation problem with different kinds of locations, where a set of locations must be visited while another set must be close enough to planned routes. Given two sets of vertices V and W, where V represents the set of vertices that may be visited and W is a set of vertices that must be covered by up to m vehicles, the m‐CTP problem is to minimize vehicle routes on a subset of V including T, which represents the subset of vertices that must be visited through the use of potential locations in V. The variant of m‐CTP without a route‐length constraint is treated in this paper. To tackle this problem, we propose a variable neighborhood search heuristic based on variable neighborhood descent method. Experiments were conducted using the datasets based on traveling salesman problem library instances.     

Variable neighborhood search for multi-objective resource allocation problems

The Resource Allocation Problem (RAP) is a classical problem in the field of operations management that has been broadly applied to real problems such as product allocation, project budgeting, resource distribution, and weapon-target assignment. In addition to focusing on a single objective, the RAP may seek to simultaneously optimize several expected but conflicting goals under conditions of resources scarcity. Thus, the single-objective RAP can be intuitively extended to become a Multi-Objective Resource Allocation Problem (MORAP) that also falls in the category of NP-Hard. Due to the complexity of the problem, metaheuristics have been proposed as a practical alternative in the selection of techniques for finding a solution. This study uses Variable Neighborhood Search (VNS) algorithms, one of the extensively used metaheuristic approaches, to solve the MORAP with two important but conflicting objectives—minimization of cost and maximization of efficiency. VNS searches the solution space by systematically changing the neighborhoods. Therefore, proper design of neighborhood structures, base solution selection strategy, and perturbation operators are used to help build a well-balanced set of non-dominated solutions. Two test instances from the literature are used to compare the performance of the competing algorithms including a hybrid genetic algorithm and an ant colony optimization algorithm. Moreover, two large instances are generated to further verify the performance of the proposed VNS algorithms. The approximated Pareto front obtained from the competing algorithms is compared with a reference Pareto front by the exhaustive search method. Three measures are considered to evaluate algorithm performance: D1_R, the Accuracy Ratio, and the number of non-dominated solutions. The results demonstrate the practicability and promise of VNS for solving multi-objective resource allocation problems.     

Heuristics for dynamic and stochastic routing in industrial shipping

Maritime transportation plays a central role in international trade, being responsible for the majority of long-distance shipments in terms of volume. One of the key aspects in the planning of maritime transportation systems is the routing of ships. While static and deterministic vehicle routing problems have been extensively studied in the last decades and can now be solved effectively with metaheuristics, many industrial applications are both dynamic and stochastic. In this spirit, this paper addresses a dynamic and stochastic maritime transportation problem arising in industrial shipping. Three heuristics adapted to this problem are considered and their performance in minimizing transportation costs is assessed. Extensive computational experiments show that the use of stochastic information within the proposed solution methods yields average cost savings of 2.5% on a set of realistic test instances.     

The capacitated vehicle routing problem with stochastic demands and time windows

The capacitated vehicle routing problem with stochastic demands and time windows is an extension of the capacitated vehicle routing problem with stochastic demands, in which demands are stochastic and a time window is imposed on each vertex. A vertex failure occurring when the realized demand exceeds the vehicle capacity may trigger a chain reaction of failures on the remaining vertices in the same route, as a result of time windows. This paper models this problem as a stochastic program with recourse, and proposes an adaptive large neighborhood search heuristic for its solution. Modified Solomon benchmark instances are used in the experiments. Computational results clearly show the superiority of the proposed heuristic over an alternative solution approach.     

Variable neighborhood search for the pharmacy duty scheduling problem

In this paper, we study on the Pharmacy Duty Scheduling (PDS) problem, where a subset of pharmacies should be on duty on national holidays, at weekends and at nights in order to be able to satisfy the emergency drug needs of the society. PDS problem is a multi-period p-median problem with special side constraints and it is an NP-Hard problem. We propose four Variable Neighborhood Search (VNS) heuristics. The first one is the basic version, BVNS. The latter two, Variable Neighborhood Decomposition Search (VNDS) and Variable Neighborhood Restricted Search (VNRS), aim to obtain better results in less computing time by decomposing or restricting the search space. The last one, Reduced VNS (RVNS), is for obtaining good initial solutions rapidly for BVNS, VNDS and VNRS. We test BVNS, VNRS and VNDS heuristics on randomly generated instances and report the computational test results. We also use VNS heuristics on real data for the pharmacies in central İzmir and obtain significant improvements.     

A hybrid metaheuristic approach for the rollon–rolloff vehicle routing problem

This paper discusses the rollon–rolloff vehicle routing problem, a sanitation routing problem in which large containers are left at customer locations such as construction sites and shopping centers. Customers dump their garbage into large waste containers and request for waste treatment services. Tractors then transport a container at a time between customer locations, disposal facility, and depot. The objective of the problem is to determine routes that minimize the number of required tractors and their deadhead time to serve all given customer demands. We propose a hybrid metaheuristic approach that consists of a large neighborhood search and various improvement methods to solve the problem. The effectiveness of the proposed approach is demonstrated by computational experiments using benchmark data. New best-known solutions are found for 17 problems out of 20 benchmark instances.     

Two-machine flow shop scheduling problem with blocking,multi-task flexibility of the first machine,and preemption

Blocking flow shop scheduling problem has been extensively studied in recent years; however, some applications mentioned for this problem have some additional characteristics that have not been well considered. Multi-task flexibility of machines and preemption are two of such characteristics. Multi-task flexible machines are capable of processing the operations of at least one other machine in the system. In addition, if preemption is allowed, the solution space grows, and solutions that are more efficient may be obtained. In this study, the two-machine flow shop scheduling problem with blocking, multi-task flexibility of the first machine, and preemption is investigated by considering the minimization of makespan as criterion. It is proved that the complexity of the problem is strongly NP-hard. Because of preemption and multi-task flexibility, there are infinite schedules for each sequence; however, it is shown that a dominant schedule can be defined for each sequence. Two mathematical models are proposed for optimally solving the small-sized instances. Furthermore, a variable neighborhood search algorithm (VNS) and a new variant of it, namely, dynamic VNS (DVNS), are presented to find high quality solutions for large-sized instances. Unlike the VNS algorithm, the DVNS algorithm does not need tuning for the shaking phase. Nevertheless, computational results show that DVNS has even a slightly better performance. The VNS and DVNS algorithms are also compared with some of the best-performing metaheuristics already developed for the flow shop scheduling problem with blocking and minimization of makespan as criterion. Computational results reveal that both algorithms are superior to the others for large-sized instances.     

Variable neighborhood search algorithm for heterogeneous traveling repairmen problem with time windows

The focus of this paper is generalized traveling repairman problem (TRP), a special case of the well known and well studied traveling salesman problem (TSP). Because of its specific objective function, that minimizes the sum of overall time all clients wait for until the end of a service, TRP has great applicability potential in client oriented practical problems. Therefore it has been known in literature as traveling deliveryman problem, minimum latency problem and cumulative capacitated vehicle routing problem. However, most studies that have treated TRP related problems have implied that only one repairman is present in the system and/or that all clients are available for service at the beginning of the planning horizon. In this paper we consider a TRP with a heterogeneous fleet of repairmen serving a set of clients whose arrival times are distributed over a planning horizon, i.e. heterogeneous TRPTW (hetTRPTW). For the hetTRPTW we present a mixed integer linear programming model, and a heuristic algorithm based on a variable neighborhood search (VNS) framework. Additionally, we propose a reduction strategy for neighborhoods in the VNS algorithm and test efficiency of implemented algorithms on four benchmark sets of problem instances. Results show that proposed algorithms could be used in real systems for solving small and moderate problem instances.