Search

The Vehicle Routing Problem with Simultaneous Pickup and Delivery (VRPSPD) is a variant of the Capacitated Vehicle Routing Problem (CVRP), in which clients require both pickup and delivery services. This paper proposes an improved particle swarm optimization algorithm based on multiple social structures for solving VRPSPD. The decoding of single particle in swarm consists two parts: the first is m dimensional (m-D) variables for m customers, and the second comprises 2n dimensions (2n-D) for n vehicles which presents vehicle route orientation. The particle is transformed to customers΄ list and vehicles matrix. A benchmark dataset is used to validate the performance of proposed algorithm. Comparing with prior works, promising results indicate that the proposed algorithm may hold high potentials for generating powerful tool for solving VRPSPD and other attributes of vehicle routing problem. [ABSTRACT FROM AUTHOR]

Integrated optimization of vehicle routing problem and container loading problem has become a research hotspot in current logistics distribution. Firstly, a mathematical model of the three-dimensional loading capacitated vehicle routing problem (3L-CVRP) is made out under the assumption of which the delivered items are rectangular, considering the rotation of items, last in first out (LIFO) rule and the loading of fragile items which are all in accordance with the realistic conditions, and the objective is to minimize the total driving distance and maximize the utilization rate of vehicle. Then, in order to solve this problem, this paper divides the process of routing and loading into two levels, and a new algorithm which combined Tabu Search (TS) with Local Search (LS) is presented. At last, the feasibility and effectiveness of the method and algorithm is proved by the adoption example. [ABSTRACT FROM AUTHOR]

Cooperative multi-agent systems are rapidly growing subclass of the multi-agent systems where autonomous components allow to built and use several agent types acting in parallel while cooperatively solving a task. Possible form of such cooperation may be based, for example, on adaptive memory methods, where partial elements of good solutions are stored and next combined to create new complete solutions. Alternative possibility forms central memory approaches, where complete elite solutions are exchanged among various heuristics. Moreover, cooperatively solving a task is often combined with learning mechanism, where agents adapt their behavior to the new conditions of environment during the process of solving the problem. The goal of the paper is to propose a dedicated cooperative multi-agent system for solving the Vehicle Routing Problem with a reinforcement learning mechanism implemented in it. [ABSTRACT FROM AUTHOR]

Most of previous studies on vehicle routing problems assume that traversal cost of each edge is simply equivalent to a constant number. Unfortunately, the models of this kind can not be applied in China because toll per kilometer of Chinese expressways varies with vehicle΄s weight. Motivated by rapidly increasing market of expressway transportation in China, we address a new and special vehicle routing problem that takes a single vehicle and its weight into account. To solve this problem practically, we provide a branch-and-bound algorithm with a well-designed lower bound. This algorithm can deal with any toll scheme in which toll per unit distance monotonically increases with weight. Computational results show that test instances with up to 42 vertices can be solved in reasonable computing time. [ABSTRACT FROM AUTHOR]

The problem discussed in this paper is similar to the Vehicle Routing Problem (VRP), however new contributions are proposed. In this work a heuristic algorithm is proposed to determine the set of the Bus Stops. A new approach is proposed to construct digital maps containing the roads where the vehicles will be able to travel, since there are no digital maps of these regions. The real distances between the points are calculated and the heuristics Location Based Heuristic with some additional features was used to propose the new routes. The algorithm was named by Adapted Location Based Heuristic (ALBH). The School Transportation Problem was implemented in the State of Parana for 399 cities. We present here the results obtained for 10 of the 399 cities. The results obtained by using this approach showed improvement in daily distance performed and in the amount of the vehicles used to do the job. [ABSTRACT FROM AUTHOR]

Firstly, the paper establishes a mathematical model for single depot and heterogeneous fleet vehicle routing problem (SHVRP) according to the actual situation of Zhengzhou Coal Electricity Material Supply and Marketing Limited Company in China, then based on the model, uses improved genetic algorithm(IGA) to optimize the vehicle routing problem (VRP) of Zhengzhou Coal Electricity Material Supply and Marketing Limited Company, finally by comparing the performance of IGA with classical heuristics algorithm (CHA) and sweeping algorithm(SA) in transportation cost, the number of used vehicle and computing time, the results show that CHA obtains the best objective function value, SA takes the second place, and CHA is the poorest; however, from the number of used vehicles, the optimum solution of CHA uses the least vehicles, followed by SA and IGA; but CHA is most efficient on computing time, the time needed for calculation is only two fifth of that of SA, two twenty five of that of IGA. [ABSTRACT FROM AUTHOR]

In this paper we study the impact of different index structures used within hybrid solution approaches for vehicle routing problems with hard feasibility checks. We examine the case of the vehicle routing problem with two-dimensional loading constraints, which combines the loading of freight into the vehicles and the routing of the vehicles to satisfy the demands of the customers. The problem is solved by a variable neighborhood search for the routing part, in which we embed an exact procedure for the loading subproblem. The contribution of the paper is threefold: i) Four different index mechanisms for managing the subproblems are implemented and tested. It is shown that simple index structures tend to lead to better solutions than more powerful albeit complex ones, when using the same runtime limits. ii) The problem of balancing the CPU budget between exploration of different solutions and exact solution of the loading subproblem is investigated; experiments show that solving exactly hard subproblems can lead to better solution quality over the whole solution process. iii) New best results are presented on existing benchmark instances. [ABSTRACT FROM AUTHOR]

Cooperation as a problem-solving strategy is widely used to build methods addressing complex hard optimization problems. It involves a set of highly autonomous agents, each implementing a particular solution method. Agents cooperate during the process of solving the problem. The main goal of the paper is to evaluate to what extent a mode of cooperation (synchronous or asynchronous) between a number of optimization agents cooperating through sharing a central memory influences the quality of solutions while solving instances of the Vehicle Routing Problem. [ABSTRACT FROM AUTHOR]

Recently, a number of swarm intelligence algorithms based on the behaviour of the bees have been presented. These algorithms are divided, mainly, in two categories according to the bees΄ behaviour in the nature, the foraging behaviour and the mating behaviour. The most important approaches that simulate the foraging behaviour of the bees are the Artificial Bee Colony algorithm, the Virtual Bee algorithm, the Bee Colony Optimization algorithm, the BeeHive algorithm, the Bee Swarm Optimization algorithm and the Bees algorithm. Contrary to the fact that there are many algorithms that are based on the foraging behaviour of the bees, the main algorithm proposed based on the mating behaviour is the Honey Bees Mating Optimization algorithm. This chapter introduces a new algorithmic nature inspired approach based on Bumble Bees Mating Optimization for successfully solving the Vehicle Routing Problem. Bumble Bees Mating Optimization algorithm is a new population-based swarm intelligence algorithm that simulates the mating behaviour that a swarm of bumble bees perform. Two sets of benchmark instances are used in order to test the proposed algorithm with very satisfactory results. [ABSTRACT FROM AUTHOR]

The Vehicle Routing Problem with Time Windows is a complex combinatorial optimization problem which can be seen as a fusion of two well known sub-problems: the Travelling Salesman Problem and the Bin Packing Problem. Its main objective is to find the lowest-cost set of routes to deliver demand, using identical vehicles with limited capacity, to customers with fixed service time windows. In this paper, we consider the minimization of the number of routes and the total cost simultaneously. Although previous evolutionary studies have considered this problem, none of them has focused on the similarity of solutions in the population. We propose a method to measure route similarity and incorporate it into an evolutionary algorithm to solve the bi-objective VRPTW. We have applied this algorithm to a publicly available set of benchmark instances, resulting in solutions that are competitive or better than others previously published. [ABSTRACT FROM AUTHOR]

Public transport systems are generally organized in a static, a priori way. In such systems, the demand must be adapted to the offer. In this paper, we propose a model based on self-organization in order to dispatch a fleet of vehicles in a purely dynamic Transportation On Demand system (TOD). Our proposal consists in a decentralized approach and a multi-agent system (MAS) to model the environment. This will tackle the problem of vehicles over-concentration or the lack of service in certain areas of the city. We demonstrate that our model addresses these problems by providing vehicle agents, for a given request, to make the final decision thanks to a negotiation process and to calculate overcosts according to an original insertion heuristic. [ABSTRACT FROM AUTHOR]

Vehicle Routing Problem(VRP) is a well known NP-hard problem, where an optimal solution to the problem cannot be achieved in reasonable time, as the problem size increases. Due to this problem, many researchers have proposed a heuristic using a local search. In this paper, we propose the Constraint Satisfaction Problem(CSP) model in Large Neighborhood Search. This model enables us to reduce the size of local search space. In addition, it enables the easy handling of many constraints in the real-world. [ABSTRACT FROM AUTHOR]

The main purpose of this study is to find out a good solution to the vehicle routing problem considering heterogeneous vehicles. This problem tries to solve the generation of paths and the assignment of buses on these routes. The objective of this problem is to minimize the number of vehicles required and to maximize the number of demands transported. This paper considers a Memetic Algorithm for the vehicle routing problem with heterogeneous fleet for any transport problem between many origins and many destinations. A Memetic Algorithm always maintains a population of different solutions to the problem, each of which operates as an agent. These agents interact between themselves within a framework of competition and cooperation. Extensive computational tests on some instances taken from the literature reveal the effectiveness of the proposed algorithm. [ABSTRACT FROM AUTHOR]

In this paper a certain modification of an evolutionary algorithm is characterized, which is intended for planning a schedule for tanker drivers working for a petrol base. The description of a computational algorithm is presented, starting from the description of a particular genotype and phenotype. The most important element of the algorithm is the procedure of projection of the genotype on the set of phenotypes based on the Baldwin Effect. The final part of the paper presents computational tests and plans for the future. [ABSTRACT FROM AUTHOR]

We consider the Vehicle Routing Problem with time windows where travel times are triangular fuzzy numbers. The weighted possibility and necessity measure of fuzzy relations is used to specify a confidence level at which it is desired that the travel times to reach each customer fall into their time windows. In this paper we propose and analyze a solution procedure consisting in hybridizing a Variable Neighborhood Search (VNS) and a Greedy Randomize Adaptive Search Procedure (GRASP) for the corresponding optimization problem. [ABSTRACT FROM AUTHOR]

In Operation Research, Branch and Bound is one of the basic methods to solve Integer programming (IP) problems. According to dividing property of branch and bound, parallel algorithms for solving Integer Programming are common. In this paper, a new parallel branch and bound algorithm is proposed for muli-computers. This algorithm instead using of shared memory multi-processor environment, uses multi computers and dynamic load balancing. As well as reduce drastically the intercommunication between processes. This algorithm is implemented for well known Capacitated Vehicle Routing Problem (CVRP). In addition, our results are quite good comparing to other algorithms. [ABSTRACT FROM AUTHOR]

This paper presents research on the Vehicle Routing Problem (VRP) using a sweep heuristic method with 2-opt exchange and traveling salesman tours and an integer programming model for split delivery VRP model to select the best route to pick up and delivery customers from/to desired destination and depot. The modeling language, AMPL with CPLEX is used to develop the model and implement the sweep heuristic. The research found that the integer programming model produced the optimal result for some cases and failed to produce the optimal result for some cases. However, the sweep heuristic gave good solutions for all cases within a small amount of computational time. The research also investigated sensitivity analysis with respect to the vehicle capacity. The results indicate a savings in number of vehicle used with a small increase in vehicle capacity. The case study of University of The Thai Chamber of Commerce (UTCC) which provides bus services to pick up and deliver staff from/to home and university is selected to present in this paper. [ABSTRACT FROM AUTHOR]

This paper proposes a new solution to the vehicle routing problem with time windows using an evolution strategy adopting viral infection. The problem belongs to the NP-hard class and is very difficult to solve within practical time limits using systematic optimization techniques. In conventional evolution strategies, a schema with a high degree-of-fitness produced in the process of evolution may not be inherited when the fitness of the individual containing the schema is low. The proposed method preserves the schema as a virus and uses it by the infection operation in successive generations. Experimental results using extended Solomon΄s benchmark problems with 1000 customers proved that the proposed method is superior to conventional methods in both its rates of searches and the probability of obtaining solutions. [ABSTRACT FROM AUTHOR]

The paper deals with a self-organizing system in a evolutionary framework applied to the Euclidean Vehicle Routing Problem (VRP). Theoretically, self-organization is intended to allow adaptation to noisy data as well as to confer robustness according to demand fluctuation. Evolution through selection is intended to guide a population based search toward near-optimal solutions. To implement such principles to address the VRP, the approach uses the standard self-organizing map algorithm as a main operator embedded in a evolutionary loop. We evaluate the approach on standard benchmark problems and show that it performs better, with respect to solution quality and/or computation time, than other self-organizing neural networks to the VRP presented in the literature. As well, it substantially reduces the gap to some classical Operations Research heuristics. [ABSTRACT FROM AUTHOR]

The article describes a study on vehicle routing problems under multiple objectives. In particular, we investigate the effectiveness of different approaches when assigning orders to vehicles. The resulting clustering problem is studied within a general framework for multi-objective vehicle routing problems where different vehicle agents place bids for orders which are offered on a marketplace. This marketplace gathers information about the current situation and provides the basis for the resolution of the allocation problem. By implementing different specialized but interacting software agents, an adaptation of the concept to various configurations of the studied problem is possible. Experimental investigations of different assignment logics on benchmark instances have been carried out and numerical results are reported. In brief, a tendency towards a particular clustering approach can be observed. [ABSTRACT FROM AUTHOR]

A vehicle routing problem which reduces to an NP-complete set-partitioning problem is considered. Three parallel algorithms for simulated annealing, i.e. the independent, semi-independent and co-operating searches are investigated. The objective is to improve the accuracy of solutions to the problem by applying parallelism. The accuracy of a solution is meant as its proximity to the optimum solution. The empirical evidence supported by the statistical analysis indicate that co-operation of processes in parallel simulated annealing yields more accurate solutions to the vehicle routing problem as compared to the case when the processes run independently or semi-independently. [ABSTRACT FROM AUTHOR]