A genetic algorithm for the simultaneous delivery and pickup problems with time window

This paper concerns a Simultaneous Delivery and Pickup Problem with Time Windows (SDPPTW). A mixed binary integer programming model was developed for the problem and was validated. Due to its NP nature, a co-evolution genetic algorithm with variants of the cheapest insertion method was proposed to speed up the solution procedure. Since there were no existing benchmarks, this study generated some test problems which revised from the well-known Solomon’s benchmark for Vehicle Routing Problem with Time Windows (VRPTW). From the comparison with the results of Cplex software and the basic genetic algorithm, the proposed algorithm showed that it can provide better solutions within a comparatively shorter period of time.     

An ant colony system (ACS) for vehicle routing problem with simultaneous delivery and pickup

In this paper we use an ant colony system (ACS) algorithm to solve the vehicle routing problem with simultaneous delivery and pickup (VRPSDP) which is a combinatorial optimization problem. ACS is an algorithmic approach inspired by the foraging behavior of real ants. Artificial ants are used to construct a solution for the problem by using the pheromone information from previously generated solutions. The proposed ACS algorithm uses a construction rule as well as two multi-route local search schemes. The algorithm can also solve the vehicle routing problem with backhaul and mixed load (VRPBM). An extensive numerical experiment is performed on benchmark problem instances available in literature. It is found that ACS gives good results compared to the existing algorithms.     

A particle swarm optimization for the vehicle routing problem with simultaneous pickup and delivery

This paper proposes a formulation of the vehicle routing problem with simultaneous pickup and delivery (VRPSPD) and a particle swarm optimization (PSO) algorithm for solving it. The formulation is a generalization of three existing VRPSPD formulations. The main PSO algorithm is developed based on GLNPSO, a PSO algorithm with multiple social structures. A random key-based solution representation and decoding method is proposed for implementing PSO for VRPSPD. The solution representation for VRPSPD with n customers and m   vehicles is a (n+2m)$(n+2m)$-dimensional particle. The decoding method starts by transforming the particle to a priority list of customers to enter the route and a priority matrix of vehicles to serve each customer. The vehicle routes are constructed based on the customer priority list and vehicle priority matrix. The proposed algorithm is tested using three benchmark data sets available from the literature. The computational result shows that the proposed method is competitive with other published results for solving VRPSPD. Some new best known solutions of the benchmark problem are also found by the proposed method.     

A hybrid discrete particle swarm optimization for vehicle routing problem with simultaneous pickup and delivery

Vehicle routing problem (VRP) is an important and well-known combinatorial optimization problem encountered in many transport logistics and distribution systems. The VRP has several variants depending on tasks performed and on some restrictions, such as time windows, multiple vehicles, backhauls, simultaneous delivery and pick-up, etc. In this paper, we consider vehicle routing problem with simultaneous pickup and delivery (VRPSPD). The VRPSPD deals with optimally integrating goods distribution and collection when there are no precedence restrictions on the order in which the operations must be performed. Since the VRPSPD is an NP-hard problem, we present a heuristic solution approach based on particle swarm optimization (PSO) in which a local search is performed by variable neighborhood descent algorithm (VND). Moreover, it implements an annealing-like strategy to preserve the swarm diversity. The effectiveness of the proposed PSO is investigated by an experiment conducted on benchmark problem instances available in the literature. The computational results indicate that the proposed algorithm competes with the heuristic approaches in the literature and improves several best known solutions.     

Development of timed Colour Petri net simulation models for air cargo terminal operations

This paper presents the development and the application of simulation models for air cargo terminal operations. As air cargo volume is fast increasing in recent years, air cargo terminals which handle cargos for carriers face challenges to streamline their operations. Air cargo terminals employ diverse storage media and are also equipped with various material handling equipments. Due to the complex and stochastic nature of terminal operations, which makes formulation of analytical model difficult, in this study, simulation models are developed to analyze the air cargo terminal operations. We first employ timed CPN (Colour Petri nets) to model the terminal operations, and then the corresponding simulation model will be developed. In order to validate this simulation model, we run the model based on actual cargo retrieval schedules obtained from an air cargo terminal. The results show that this model provides a good estimate of the terminal performance. The model is then employed to analyze the performance of the airline assignment policy for the objective of minimizing the cargo processing times, and the results show that the proposed policy significantly improves the operational performance of air cargo terminals. Second, the simulation model is employed to analyze the performance of an AS/RS (Automated Storage and Retrieval System), and the performance of the proposed storage policy is compared with that of the current policy. The simulation experiment also validates the optimal parameter value from the analytic model. The developed models simulate air cargo terminal operations effectively and efficiently, and will aid future studies in the design and control of terminal operations.     

Integrated product and process designenvironment tool for manufacturing T/R modules

We present a decision-making assistant tool for an integrated product and process design environment for manufacturing applications. Specifically, we target microwave modules that use electro-mechanical components and require optimal solutions to reduce cost, improve quality, and gain leverage in time to market the product. This tool will assist the product and process designer to improve their productivity and enable them to cooperate and coordinate their designs through a common design interface. We consider a multiobjective optimization model that determines components and processes for a given conceptual design for microwave modules. This model outputs a set of solutions that the Pareto optimal concerning cost, quality, and other metrics. In addition, we identify system integration issues for manufacturing applications, and propose an architecture that will serve as a building block to our continuing research in virtual manufacturing applications.     

A tabu search heuristic for the single vehicle pickup and delivery problem with time windows

The single vehicle pickup and delivery problem with time windows is a generalization of the traveling salesman problem. In such a problem, a number of transportation requests have to be satisfied by one vehicle, each request having constraints to respect: a pickup at its origin and a delivery at its destination, and a time window at each location. The capacity of the vehicle has to be respected. The aim is to minimize the total distance traveled by the vehicle. A number of exact and approximate solution methods exists in the literature, but to the authors knowledge none of them make use of metaheuristics, still promising with other vehicle routing problems. In this paper we present tabu search and probabilistic tabu search. Results obtained on classical traveling salesman problems and a class of randomly generated instances indicate that our approach often produces optimal solutions in a relatively short execution time.