This dissertation examines the Split Delivery Vehicle Routing Problem (SDVRP), a relaxed version of classical capacitated vehicle routing problem (CVRP) in which the demand of any client can be split among the vehicles that visit it. We study both scenarios of the SDVRP in this dissertation. For the SDVRP with a fixed number of the vehicles, we provide a Two-Stage algorithm. This approach is a cutting-plane based exact method called Two-Stage algorithm in which the SDVRP is decomposed into two stages of clustering and routing. At the first stage, an assignment problem is solved to obtain some clusters that cover all demand points and get the lower bound for the whole problem; at the second stage, the minimal travel distance of each cluster is calculated as a traditional Traveling Salesman Problem (TSP), and the upper bound is obtained. Adding the information obtained from the second stage as new cuts into the first stage, we solve the first one again. This procedure stops when there are no new cuts to be created from the second stage. Several valid inequalities have been developed for the first stage to increase the computational speed. A valid inequality is developed to completely solve the problem caused by the index of vehicles. Another strong valid inequality is created to provide a valid distance lower bound for each set of demand points. This algorithm can significantly outperform other exact approaches for the SDVRP in the literature. If the number of the vehicles in the SDVRP is a variable, we present a column generation based branch and price algorithm. First, a restricted master problem (RMP) is presented, which is composed of a finite set of feasible routes. Solving the linear relaxation of the RMP, values of dual variables are thus obtained and passed to the sub-problem, the pricing problem, to generate a new column to enter the base of the RMP and solve the new RMP again. This procedure repeats until the objective function value of the pricing problem is greater than or equal to zero (for minimum problem). In order to get the integer feasible (optimal) solution, a branch and bound algorithm is then performed. Since after branching, it is not guaranteed that the possible favorable column will appear in the master problem. Therefore, the column generation is performed again in each node after branching. The computational results indicate this approach is promising in solving the SDVRP in which the number of the vehicles is not fixed.

In this thesis, we study the role of interdiction in the Vehicle Routing Problem (VRP), which naturally arises in humanitarian logistics and military applications. We assume that in a general network, each arc has a chance to be interdicted. When interdiction happens, the vehicle traveling on this arc is lost or blocked and thus unable to continue the trip. We model the occurrence of interdiction as a given probability and consider the multi-period expected delivery. Our objective is to minimize the total travel cost or to maximize the demand fulfillment, depending on the supply quantity. This problem is called the Vehicle Routing Problem with Interdiction (VRPI). We first prove that the proposed VRPI problems are NP-hard. Then we show some key analytical properties pertaining to the optimal solutions of these problems. Most importantly, we examine Dror and Trudeau's property applied to our problem setting. Finally, we present efficient heuristic algorithms to solve these problems and show the effectiveness through numerical studies. / Thesis / Master of Science (MSc)

The master's thesis deals with the new modification of vehicle routing problem -- 3PL vehicle routing problem with heterogeneous fleet and split delivery. In addition to classical vehicle routing problem, we consider a heterogeneous suppliers fleet and also external carrier, which charges a fixed value per unit of transported goods. The reader is first introduces to vehicle routing problem, its history and possible solutions. Furthermore, the reader is acquainted with logistics and logistics providers. In the main part of this thesis is described 3PL vehicle routing problem and its mathematical model. At first we try to get optimal solution via CPLEX solver. But since this is an NP-hard task, heuristic method is proposed (in two variants) for solving this problem. The heuristic is then tested on the selected test tasks. Results obtained using the proposed heuristics are compared with the optimal solution. Even larger problems are then solved using this heuristics. In the end other modifications and possible improvements of this heuristic method are proposed.

Split delivery vehicle rating problem is one of the most studied combinatorial optimization problems in operations research. According to the mathematical difficultness, there should be many problems to find the optimal solution. Therefore, there are many exact algorithms and heuristics, which tries to find the best solution in the short period of time. The theoretical part of this thesis describes the basic facts of the split delivery vehicle routing problem and its heuristics. The practical part focuses on the practical usage of the split delivery vehicle routing problem. The main goals of this thesis are the practical usage of this vehicle routing problem and assistance in strategic decision establishing of the secondary store.

In this thesis we report several of delivery problems. Here it is mostly describe Vehicle Routing Problem and Split Delivery Problem as suitable methods for the case study of the company Baťa a.s.In this thesis we used one of the most sofisticated software Roadnet Transportation Suite as effective program for distribution and planning routes.Finally we construct analysis as a support to find the optimal solution for the final strategical decision of the company Baťa a.s.

This thesis focuses on a description of the split delivery vehicle routing problem (SDVRP), in which the restriction that each customer has to be visited exactly once is not assumed, contrary to the classical vehicle routing problem, and split deliveries are allowed. Considering the fact that the split delivery vehicle routing problem in NP-hard, a number of heuristic algorithms proposed in the literature are presented. Computational experiments are reported and the results show that the largest benefits of split deliveries are obtained in case of instances with fairly specific characteristics and also several drawbacks of implemented Tabu Search algorithm (SPLITABU) are point out.

Nowadays, when great emphasis is put on cost savings, transport optimization is necessary part of every company life in which transportation costs produce significant part. There are optimization methods and possibilities presented in this thesis. In the first chapter there are explained methods such as the travelling salesman problem, the vehicle routing problem, the multiple vehicle routing problem and the split delivery vehicle routing problem and then the reader gets to know the heuristics methods in the chapter two where description of the nearest neighbour method, Clarke-Wright method and split delivery heuristic is mentioned. In the last but one chapter author applies previous methods on concrete distribution arranged by Movianto Česká republika s.r.o. on 5th September, 2013. Based on gained outputs, analysis and comparison of results (including the original distribution) are provided in the fourth chapter. Obtained results of analysis lead to recommendation on how the company should plan its future distribution.

No description available.

This diploma thesis describes a logistic problem of the company JACER-CZ Ltd. The main focus is on identifying optimal routes about the Euro pallets distribution. The Euro pallets are standardized at length replaceable transport pallets which are in Europe. The aim of this thesis is to find a solution which will meet requirements of all thirteen customers and simultaneously a total route length of all vans will be minimalized. At first there is the mathematical model about the delivery assignment with the split delivery vehicle calculated by solvers CPLEX and Gurobi. Then the original and the modified example is solved manually by heuristic algorithms. It is concerned the nearest neighbour algorithm, savings algorithm, the insertion algorithm and the heuristic method for the split delivery vehicle routing problem.

The aim of this work is to show the application of operational research on an example that is put into practise and to show the usabillity of this science field. The problem solved will be the Vehicle routing problem with split delivery. The whole process of solving this issue is described in the text. From the income data and automatised data aquisition from publicly acessible resources for the distance matrix to the created mathemathical model for this issue together with the implementation in SW Lingo. Furthermore, in my work classic distribution problem of linear programming in connection to the solved issue are described. Beside that three mathematical models are shown that are occyupying with this type of delivery. They can not be used for fading the solution to this issue as they include certain requirements or conditions which are not taken into account by the given models.