To see the other types of publications on this topic, follow the link: Vehicle-routing-Problem / Heuristik.
Dissertations / Theses on the topic 'Vehicle-routing-Problem / Heuristik'
Create a spot-on reference in APA, MLA, Chicago, Harvard, and other styles
Consult the top 50 dissertations / theses for your research on the topic 'Vehicle-routing-Problem / Heuristik.'
Next to every source in the list of references, there is an 'Add to bibliography' button. Press on it, and we will generate automatically the bibliographic reference to the chosen work in the citation style you need: APA, MLA, Harvard, Chicago, Vancouver, etc.
You can also download the full text of the academic publication as pdf and read online its abstract whenever available in the metadata.
Browse dissertations / theses on a wide variety of disciplines and organise your bibliography correctly.
1
Doerner, Karl, Manfred Gronalt, Richard F. Hartl, Marc Reimann, Christine Strauß, and Michael Stummer. "SavingsAnts for the vehicle routing problem." SFB Adaptive Information Systems and Modelling in Economics and Management Science, WU Vienna University of Economics and Business, 2001. http://epub.wu.ac.at/1130/1/document.pdf.
Full textAbstract:
In this paper we propose a hybrid approach for solving vehicle routing problems. The main idea is to combine an Ant System (AS) with a problem specific constructive heuristic, namely the well known Savings algorithm. This differs from previous approaches, where the subordinate heuristic was the Nearest Neighbor algorithm initially proposed for the TSP. We compare our approach with some other classic, powerful meta-heuristics and show that our results are competitive.<br>Series: Report Series SFB "Adaptive Information Systems and Modelling in Economics and Management Science"
2
Reimann, Marc, Karl Doerner, and Richard F. Hartl. "Insertion based Ants for Vehicle Routing Problems with Backhauls and Time Windows." SFB Adaptive Information Systems and Modelling in Economics and Management Science, WU Vienna University of Economics and Business, 2002. http://epub.wu.ac.at/1724/1/document.pdf.
Full textAbstract:
In this paper we present and analyze the application of an Ant System to the Vehicle Routing Problem with Backhauls and Time Windows (VRPBTW). At the core of the algorithm we use an Insertion procedure to construct solutions. We provide results on the learning and runtime behavior of the algorithm as well as a comparison with a custom made heuristic for the problem.<br>Series: Report Series SFB "Adaptive Information Systems and Modelling in Economics and Management Science"
3
Gerlich, Michal. "Aplikace heuristik při řešení rozvozní úlohy." Master's thesis, Vysoká škola ekonomická v Praze, 2011. http://www.nusl.cz/ntk/nusl-73532.
Full textAbstract:
This thesis deals with solving a real case from one specific part of Operations Research -- Discrete Models. The case can be classified as Vehicle Routing Problem (VRP) which is a subset of classical Travelling Salesman Problem (TSP). The VRP is modified TSP when requirements of customers and capacities of trucks play role. The data needed for calculations were taken from the real situation of Pivovar Svijany a.s. The problem can be defined as VRP with cars with different capacities and split delivery. Even though the mathematic model of the problem is known and described in the thesis, the size of the problem is too big to be optimized. Therefore heuristic was used to solve it. Because of the good computational results in the past the savings algorithm was chosen. Its model was set using Visual Basic for Applications (VBA). The thesis (among others) analyses the sensitivity of the output on the values of the factors that can be chosen by the analyst. At the end of the thesis the best found solution is presented and the initial and the new scheme of the circles are compared.
4
Trunda, Otakar. "Implementace heuristik pro rozvozní problém s časovými okny." Master's thesis, Vysoká škola ekonomická v Praze, 2017. http://www.nusl.cz/ntk/nusl-358970.
Full textAbstract:
Vehicle Routing Problem with Time Windows is a hard optimization problem. Even though it has numerous practical applications, the question of solving it efficiently has not been satisfyingly solved yet. This thesis studies the Vehicle Routing Problem with Time Windows and presents several new algorithms for solving it. There are two heuristics presented here, as well as several more complex algorithms which use those heuristics as their components. The efficiency of presented techniques is evaluated experimentally using a set of test samples. As a part of this thesis, I have also developed a desktop application which implements presented algorithms and provides a few additional features useful for solving routing prob-lems in practice. Among others, there is a generator of pseudo-random problem instances and several visualization methods.
5
Talaei, Majid. "Heuristics for energy efficient vehicle routing problem." Thesis, Wichita State University, 2012. http://hdl.handle.net/10057/5611.
Full textAbstract:
US logistics cost of 1.397 trillion dollars in 2007, which stands for more that 10 percent of the total GDP of the country justifies any attempt of reducing it. Transportation followed by inventory-carrying and logistics administration has the greatest cost share in logistics. A tool which is very critical in transportation planning and can contribute to huge savings if used properly is Vehicle Routing Problem. Near optimum vehicle routs which are designed by outstanding heuristics and experts could contribute significantly to cost saving. Another important issue which directly affects logistics and transportation is energy consumption. Energy consumption and energy saving plans are hot topics everywhere nowadays. Issues such as green house effect, global warming effect and oil resources termination are great global concerns. This research tries to modify vehicle routing problem heuristics and make them sensitive to the issue of energy consumption. Traditional VRP heuristics and solution methods have tried to minimize total distance traveled of vehicles as the main objective function, while energy consumption minimization is the objective function of energy efficient VRP heuristics in this research. Two heuristics are modified in an “Energy Efficient” manner, nearest neighbor algorithm and saving algorithm. The proposed heuristics are examined with several benchmark problems from literature and are found to be efficient and effective both in terms of total distance travelled and energy consumption.<br>Thesis (M.S.)--Wichita State University, College of Engineering, Dept. of Industrial and Manufacturing Engineering
6
Sariklis, Dimitrios. "Open Vehicle Routing Problem : description, formulations and heuristic methods." Thesis, London School of Economics and Political Science (University of London), 1997. http://ethos.bl.uk/OrderDetails.do?uin=uk.bl.ethos.265252.
Full text
7
Escobar, Velasquez John Willmer <1980>. "Heuristic algorithms for the Capacitated Location-Routing Problem and the Multi-Depot Vehicle Routing Problem." Doctoral thesis, Alma Mater Studiorum - Università di Bologna, 2013. http://amsdottorato.unibo.it/5258/.
Full textAbstract:
The Capacitated Location-Routing Problem (CLRP) is a NP-hard problem since it generalizes two well known NP-hard problems: the Capacitated Facility Location Problem (CFLP) and the Capacitated Vehicle Routing Problem (CVRP). The Multi-Depot Vehicle Routing Problem (MDVRP) is known to
be a NP-hard since it is a generalization of the well known Vehicle Routing Problem (VRP), arising with one depot. This thesis addresses heuristics algorithms based on the well-know granular search idea introduced by Toth and Vigo (2003) to solve the CLRP and the MDVRP. Extensive computational experiments on benchmark instances for both problems have been performed to determine the effectiveness of the proposed algorithms.
This work is organized as follows:
Chapter 1 describes a detailed overview and a methodological review of the literature for the the Capacitated Location-Routing Problem (CLRP) and the Multi-Depot Vehicle Routing Problem (MDVRP).
Chapter 2 describes a two-phase hybrid heuristic algorithm to solve the CLRP.
Chapter 3 shows a computational comparison of heuristic algorithms for the CLRP.
Chapter 4 presents a hybrid granular tabu search approach for solving the MDVRP.
8
Silvestrin, Paulo Vitor. "An efficient heuristic for the multi-compartment vehicle routing problem." reponame:Biblioteca Digital de Teses e Dissertações da UFRGS, 2016. http://hdl.handle.net/10183/149656.
Full textAbstract:
Este trabalho apresenta uma variação do problema de roteamento de veículos que permite o uso de veículos com múltiplos compartimentos. A necessidade de veículos com múltiplos compartimentos surge com frequência em aplicações práticas quando uma série de produtos, que possuem diferentes qualidades ou tipo, precisam ser transportados mas não podem ser misturados. Este problema é chamado na literatura de roteamento de veículos com múltiplos compartimentos (PRVMC). Nós propomos uma heurística busca tabu implementada em uma busca local iterada para resolver este problema. Experimentos foram feitos para avaliar a performance da busca tabu iterada e os resultados obtidos foram comparados com os resultados disponíveis na literatura. O algoritimo proposto é capaz de encontrar soluções melhores e em menos tempo de processamento que as heurísticas existentes.<br>We study a variant of the vehicle routing problem that allows vehicles with multiple compartments. The need for multiple compartments frequently arises in practical applications when there are several products of different quality or type, that must be kept or handled separately. The resulting problem is called the multi-compartment vehicle routing problem (MCVRP). We propose a tabu search heuristic and embed it into an iterated local search to solve the MCVRP. In several experiments we analyze the performance of the iterated tabu search and compare it with results from the literature. We find that it consistently produces solutions that are better than existing heuristic algorithms.
9
Plášková, Pavlína. "Strategické rozhodnutí společnosti Baťa, a.s." Master's thesis, Vysoká škola ekonomická v Praze, 2008. http://www.nusl.cz/ntk/nusl-3836.
Full textAbstract:
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.
10
Almutairi, Abdulwahab. "Sim-heuristic algorithms for Robust Vehicle Routing Problem with Stochastic Demand." Thesis, University of Portsmouth, 2016. https://researchportal.port.ac.uk/portal/en/theses/simheuristic-algorithms-for-robust-vehicle-routing-problem-with-stochastic-demand(c418aed0-29a5-49f5-b191-ece4796e5827).html.
Full textAbstract:
The Vehicle Routing Problem with Stochastic Demand (VRPSD) is a fundamental problem underlying many operational challenges in the field of logistic and supply chain management. The VRPSD is a well-known NP-hard problem whereby a fleet of vehicles is located at a single depot. Each vehicle has a limited capacity and has to serve a number of customers whose actual demands are known only when the vehicle arrives at the customers’ locations. The VRPSD arises in practice whenever a company faces the problem of delivering to a set of customers, whose demands are uncertain. The solution to the VRPSD includes the optimisation of complete routing schedules whilst minimising the transportation costs (fixed costs and variable costs) to satisfy all the constraints in the problem. This study proposes three approaches: the robust routing model with sim-heuristic, randomised Iterated Greedy (IG) algorithm with Monte Carlo Simulation (MCS) and finally IG algorithm with local search to solve the VRPSD. The main aim of using the robust routing model with sim-heuristics is to build robust solutions by combining simulation and optimisation using heuristic methods. This is to handle uncertainty as well as to optimise against any worst instance that might arise due to data uncertainty. Several heuristics have been combined with simulation to deal with stochastic demand. In our version of the approach, the first one is a randomised Clarke and Wright Saving (CWS) algorithm step after which an MCS is incorporated in order to improve the final solutions of VRPSD. The second approach proposed the combination of randomised IG algorithm with MCS to be applied on the VRPSD. The final approach is to use an IG algorithm with local search, based on the aforementioned first approach, in order to improve the solutions generated. Local search has been proven to be an effective technique for obtaining good solutions. The developed robust routing model and sim-heuristic algorithms are tested on well-known benchmark instances and a real-life case study is considered in order to evaluate the effectiveness of the proposed methodologies. The computational results showed that the proposed methodologies are capable of finding useful solutions for the VRPSD and that they are good/robust for the stochastic nature of the problem instances. After computing the average costs from each instance, we also computed the best solution and found that they both could be highly promising and useful for decision makers. The results obtained are quite competitive when compared to the other algorithms found in the literature.
11
Silveira, Ulisses Eduardo Ferreira da. "Heuristic approaches to the double vehicle routing problem with multiple stacks." Universidade Federal de Viçosa, 2017. http://www.locus.ufv.br/handle/123456789/11596.
Full textAbstract:
Submitted by Reginaldo Soares de Freitas (reginaldo.freitas@ufv.br) on 2017-08-23T12:56:44Z
No. of bitstreams: 1
texto completo.pdf: 993417 bytes, checksum: af46bc7032d180cae6ecae3aaebec7c1 (MD5)<br>Made available in DSpace on 2017-08-23T12:56:44Z (GMT). No. of bitstreams: 1
texto completo.pdf: 993417 bytes, checksum: af46bc7032d180cae6ecae3aaebec7c1 (MD5)
Previous issue date: 2017-03-06<br>Coordenação de Aperfeiçoamento de Pessoal de Nível Superior<br>Em um mundo que, em tempo acelerado, tem-se tornado cada vez mais necessitado em bens consumíveis e não consumíveis, a logística no transporte destes produtos tem sido colocada à prova, sendo uma das etapas mais importantes da relação entre o processo de produção e o usuário final. Cerca de um terço dos custos logísticos desta relação (produção-usuário) são determinados pelo custo de transporte dos bens, tornando essa operação muito importante. Um novo problem surgiu a partir de um entrave encontrado numa situação prática. O Problema do Roteamento de Veículos Duplo com Múltiplas Pilhas (DVRPMS) consiste em um Problema do Caixeiro Viajante com Múltiplas Pilhas (DTSPMS) com múltiplos veículos. Os dois problemas apareceram pela necessidade urgente em otimizar o transporte intermodal em um contexto europeu. Consiste em coletar pedidos em uma região de coleta e carregá-los num conjunto de pilhas dentro de um container, que não deve ser rearranjado por razões de segurança. O container então é levado a região de entrega e os itens são entregues seguindo a política das pilhas, em que os itens do topo, coletados por último, devem ser entregues primeiro. Nesta dissertação, quatro heurísticas baseadas na busca local iterativa (ILS), na descida em vizinhança variável (VND) e no recozimento simulado (SA) são propostas. O problema foi estendido para uma versão onde há uma oferta de itens maior do que a capacidade da frota de veículos. Um método exato é proposto juntamente com outras três heurísticas baseadas no ILS, SA e na busca tabu (TS). Os algoritmos propostos foram testados em experimentos computacionais e análises estatísticas foram feitas com intenção de encontrar a melhor combinação de parâmetros para estas heurísticas. Os resultados encontrados foram bons, tendo encontrado melhores médias que a literatura atual.<br>In a world, that in a fast pace, has become increasingly needed in consumable and nonconsumable goods, the logistics in the transportation of these products has been put to the test, being one of the most important stages in the relationship between the pro-duction process and the end user. It is said that at least 30% of the costs between the industry and the end user are solely determined by the cost of transportation. A novel problem arose followed by a question that was encountered in a real-life scenario. The Double Routing Vehicle Problem with Multiple Stacks (DVRPMS) consists in a Dou-ble Traveling Salesman Problem with Multiple Stacks (DTSPMS) with multiple vehicles. Both problems appeared for the urgent need of optimizing intermodal transportation in the european context. It consists in gathering costumer inquires from a pickup region and loading them in a set of stacks inside a container that must not be rearranged for security reasons. The container moves to a delivery region and the items gathered must be delivered according the last-in-first-out policy of the stacks. In this work, four heuristics were proposed based on the Iterated Local Search (ILS), Variable Neighborhood Descent and Simulated Annealing (SA) metaheuristics. The DVRPMS was extended to a modi-fied version where the items offered are bigger than the vehicle fleet capacities. An exact model approach is proposed and three other heuristics, based on the ILS, SA and Tabu Search are proposed and tested. The approaches presented in this work were tested by computational experiments and a statistical analysis was made to chose the best com-bination of parameters. Good results were found, providing a better average than the current literature.
12
Walker, James D. "Design of vehicle routing problem domains for a hyper-heuristic framework." Thesis, University of Nottingham, 2015. http://eprints.nottingham.ac.uk/30596/.
Full textAbstract:
The branch of algorithms that uses adaptive methods to select or tune heuristics, known as hyper-heuristics, is one that has seen a large amount of interest and development in recent years. With an aim to develop techniques that can deliver results on multiple problem domains and multiple instances, this work is getting ever closer to mirroring the complex situations that arise in the corporate world. However, the capability of a hyper-heuristic is closely tied to the representation of the problem it is trying to solve and the tools that are available to do so. This thesis considers the design of such problem domains for hyper-heuristics. In particular, this work proposes that through the provision of high-quality data and tools to a hyper-heuristic, improved results can be achieved. A definition is given which describes the components of a problem domain for hyper-heuristics. Building on this definition, a domain for the Vehicle Routing Problem with Time Windows is presented. Through this domain, examples are given of how a hyper- heuristic can be provided extra information with which to make intelligent search decisions. One of these pieces of information is a measure of distance between solution which, when used to aid selection of mutation heuristics, is shown to improve results of an Iterative Local Search hyper-heuristic. A further example of the advantages of providing extra information is given in the form of the provision of a set of tools for the Vehicle Routing Problem domain to promote and measure ’fairness’ between routes. By offering these extra features at a domain level, it is shown how a hyper-heuristic can drive toward a fairer solution while maintaining a high level of performance.
13
Krčmář, Pavel. "Optimalizace rozvozu piva na Jesenicku." Master's thesis, Vysoká škola ekonomická v Praze, 2012. http://www.nusl.cz/ntk/nusl-124608.
Full textAbstract:
The thesis deals with application of models of routing problems on a real problem, beer distribution in Jesenicko region provided by Viden plus, a.s. The goal of the thesis is to optimize daily distributional routes for two vehicles with different capacities. Total distance has to be minimized respecting time and capacity limits. In case the optimal solution is not found, sub-optimal solution will be accepted. Solutions are calculated with use of the optimization software LINGO and some heuristic methods. Models of travelling salesman problem and vehicle routing problem are used to find the solutions. Results are compared to the current state of distributional routes in conclusion of the thesis.
14
Cacchiani, Valentina, Vera Hemmelmayr, and Fabien Tricoire. "A set-covering based heuristic algorithm for the periodic vehicle routing problem." Elsevier, 2014. http://dx.doi.org/10.1016/j.dam.2012.08.032.
Full textAbstract:
We present a hybrid optimization algorithm for mixed-integer linear programming, embedding both heuristic and exact components. In order to validate it we use the periodic vehicle routing problem (PVRP) as a case study. This problem consists of determining a set of minimum cost routes for each day of a given planning horizon, with the constraints that each customer must be visited a required number of times (chosen among a set of valid day combinations), must receive every time the required quantity of product, and that the number of routes per day (each respecting the capacity of the vehicle) does not exceed the total number of available vehicles. This is a generalization of the well-known vehicle routing problem (VRP). Our algorithm is based on the linear programming (LP) relaxation of a set-covering-like integer linear programming formulation of the problem, with additional constraints. The LP-relaxation is solved by column generation, where columns are generated heuristically by an iterated local search algorithm. The whole solution method takes advantage of the LP-solution and applies techniques of fixing and releasing of the columns as a local search, making use of a tabu list to avoid cycling. We show the results of the proposed algorithm on benchmark instances from the literature and compare them to the state-of-the-art algorithms, showing the effectiveness of our approach in producing good quality solutions. In addition, we report the results on realistic instances of the PVRP introduced in Pacheco et al. (2011) [24] and on benchmark instances of the periodic traveling salesman problem (PTSP), showing the efficacy of the proposed algorithm on these as well. Finally, we report the new best known solutions found for all the tested problems. (authors' abstract)
15
Wassan, Naveed Ahmed. "Meta-heuristics for the multiple trip vehicle routing problem with backhauls." Thesis, University of Kent, 2016. https://kar.kent.ac.uk/56731/.
Full textAbstract:
With the growing and more accessible computational power, the demand for robust and sophisticated computerised optimisation is increasing for logistical problems. By making good use of computational technologies, the research in this thesis concentrates on efficient fleet management by studying a class of vehicle routing problems and developing efficient solution algorithms. The literature review in this thesis looks at VRPs from various development angles. The search reveals that from the problem modelling side clear efforts are made to bring the classical VRP models closer to reality by developing various variants. However, apart from the real VRP applications (termed as 'rich' VRPs), it is also noticeable that these classical VRP based variants address merely one or two additional characteristics from the real routing problem issues, concentrating on either operational (fleet management) or tactical (fleet acquisition) aspects. This thesis certainly hopes to add to one of those good efforts which have helped in bringing the VRPs closer to reality through addressing both the operational as well as the tactical aspects. On the solution methodologies development side, the proposed research noted some considerable and impressive developments. Although, it is well established that the VRPs belong to the NP-hard combinatorial class of problems, there are considerable efforts on the development of exact methods. However the literature is full of a variety of heuristic methodologies including the classical and the most modern hybrid approaches. Among the hybrid approaches, the most recent one noted is mat-heuristics that combine heuristics and mathematical programming techniques to solve combinatorial optimisation problems. The mat-heuristics approaches appear to be comparatively in its infant age at this point in time. However this is an exciting area of research which seeks more attention in the literature. Hence, a good part of this research is devoted to the development of a hybrid approach that combines heuristics and mathematical programming techniques. When reviewing the specific literature on the VRP problems focused in this thesis, the vehicle routing problem with backhauls (VRPB) and the multiple trip vehicle routing problem (MT-VRP), there is not sufficient development on the problem modelling side in terms of bringing these two problems closer to the reality. Hence, to fill the gap this thesis introduces and investigates a new variant, the multiple trip vehicle routing problem with backhauls (MT-VRPB) that combines the above two variants of the VRP. The problem is first described thoroughly and a new ILP (Integer Linear Programming) mathematical formulation of the MT-VRPB along with its possible variations is presented. The MT-VRPB is then solved optimally by using CPLEX along with providing an illustrative example showing the validation of the mathematical formulation. As part of the contribution, a large set of MT-VRPB data instances is created which is made available for future benchmarking. The CPLEX implementation produced optimal solutions for a good number of small and medium size data instances of the MT-VRPB and generated lower bounds for all instances. The CPLEX success may be considered as modest, but the produced results proved very important for the validation of the heuristic results produced in the thesis. To solve the larger instances of the MT-VRPB, a two level VNS algorithm called 'Two-Level VNS' is developed. It was noticed from the literature that the choice of using VNS for the VRPs has increased in recent literature due to its simplicity and speed. However our initial experiments with the classical VNS indicated that the algorithm is more inclined towards the intensification side. Hence, the Two-Level VNS is designed to obtain a maximum balance of the diversification and the intensification during the search process. It is achieved by incorporating a sub-set of neighbourhood structures and a sus-set of local search refinement routines and hence, a full set of neighbourhood structures and a full set of local search refinement routines at two levels of the algorithm respectively. The algorithm found very encouraging results when compared with the solutions found by CPLEX. These findings in this thesis demonstrate the power of VNS yet again in terms of its speed, simplicity and efficiency. To investigate this new variant further, we developed an algorithm belonging to the new class of the hybrid methodologies, i.e., mat-heuristics. A hybrid collaborative sequential mat-heuristic approach called the CSMH to solve the MT-VRPB is developed. The exact method approach produced in Chapter 4 is then hybridised with the Two-Level VNS algorithm developed in Chapter 5. The overall performance of the CSMH remained very encouraging in terms of the solution quality and the time taken on average compared with the CPLEX and the Two-Level VNS meta-heuristic. To demonstrate the power and effectiveness of our methodologies, we tested the designed algorithms on the two special versions of the VRP (i.e., VRPB and MT-VRP) to assess whether they are efficient and dynamic enough to solve a range of VRP variants. Hence the Two-Level VNS and the CSMH algorithms developed to solve the MT-VRPB are adapted accordingly and implemented to solve the two above variants separately. The algorithms produced very competitive results for the benchmark data sets when compared to the best known solutions from the literature. The successful implementations of these algorithms on the three VRP models with only minor amendments prove their generalizability and their robustness. The results in this research show that significant cost savings could be obtained by choosing the right fleet size and better vehicle utilisations with multiple trips and backhauling. Hence, the research proved the justification of studying this interesting combination. Moreover, the problem modelling, efficient algorithm design and implementation, and the research results reveal some vital information and implications from the managerial point of view in terms of making the tactical (fleet acquisition) and the operational (fleet management) decisions in a more informative manner.
16
Wade, Anne Camilla. "Constructive and ant system heuristics for a class of vehicle routing problem with backhauls." Thesis, University of Birmingham, 2002. http://ethos.bl.uk/OrderDetails.do?uin=uk.bl.ethos.269773.
Full text
17
Cheng, Lin. "A genetic algorithm for the vehicle routing problem with time windows /." Electronic version (PDF), 2005. http://dl.uncw.edu/etd/2005/chengl/lincheng.pdf.
Full text
18
Juříčková, Ivana. "Optimalizace tras při rozvozu europalet." Master's thesis, Vysoká škola ekonomická v Praze, 2014. http://www.nusl.cz/ntk/nusl-194529.
Full textAbstract:
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.
19
Seixas, Michel Povlovitsch. "Heuristic and exact methods applied to a rich vehicle routing and scheduling problem." Universidade de São Paulo, 2013. http://www.teses.usp.br/teses/disponiveis/3/3135/tde-09072014-111258/.
Full textAbstract:
This study considers a vehicle routing problem with time windows, accessibility restrictions on customers and a fleet that is heterogeneous with regard to capacity, average speed and cost. A vehicle can perform multiple routes per day, all starting and ending at a single depot, and it is assigned to a single driver, whose total work hours are limited. The available fleet is divided into an owned fleet, for which a variable cost is incurred, and a chartered fleet, for which only a fixed cost is incurred for each vehicle used. A column generation algorithm embedded in a branch-and-bound framework is proposed. The column generation pricing subproblem required a specific elementary shortest path problem with resource constraints algorithm to address the possibility for each vehicle performing multiple routes per day and to address the need to determine the workdays start time within the planning horizon. To make the algorithm efficient, a constructive heuristic and a learning metaheuristic algorithm based on tabu search were also developed. Both were used on branch-and-bound tree nodes to generate a good initial solution to the linear restricted master problem; particularly, to find a good initial primal bound to the branch-and-bound tree.<br>Este estudo aborda um problema de roteirização de veículos com janelas de tempo, restrições de acessibilidade nos clientes e uma frota que é heterogênea em relação à capacidade de carga, velocidade média de deslocamento e custo. Um veículo pode percorrer múltiplas rotas por dia, todas começando e terminando em um mesmo depósito, e está designado a um único motorista, cujo total de horas trabalhadas no dia está limitado a um valor máximo. A frota disponível é dividida em uma frota própria, para a qual um custo variável é incorrido, e uma frota de freteiros, para a qual apenas um custo fixo é incorrido para cada veículo utilizado. Um algoritmo baseado em geração de colunas, integrado a um procedimento de branch-and-bound, é proposto neste estudo. O subproblema de precificação da geração de colunas requereu um algoritmo específico para o problema do caminho mínimo elementar com restrições sobre recursos capaz de lidar com a possibilidade de cada veículo percorrer múltiplas rotas por dia e capaz de lidar com a necessidade de determinar o instante de início do dia de trabalho do motorista dentro do horizonte de planejamento. Para tornar o algoritmo eficiente, uma heurística construtiva e uma heurística de melhoria baseada em busca tabu também foram desenvolvidos. Ambos são utilizados nos nós da árvore de branch-and-bound para gerar boas soluções iniciais para o problema mestre restrito da geração de colunas; particularmente, para encontrar um bom limitante primal inicial para a árvore de branch-and-bound.
20
Vršecká, Renáta. "Optimalizace rozvozu piva společnosti Heineken." Master's thesis, Vysoká škola ekonomická v Praze, 2009. http://www.nusl.cz/ntk/nusl-76523.
Full textAbstract:
This thesis deals with real logistic problem of the Heineken CZ Company. The company sets down an itinerary for each vehicle to distribute its goods to particular customers on daily basis. These itineraries are created manually, only with the skill of experienced driver. The goal of this thesis is to find a solution with an algorithm, which will be able to set optimal itineraries of all vehicles, so the total distance and therefore operating costs are minimized, with only the knowledge of distances between each two nodes.
21
Hajarat, Mutaz Othman Aref. "Heuristics for the fleet size and mix vehicle routing problem with backhauls." Thesis, University of Kent, 2009. https://ethos.bl.uk/OrderDetails.do?uin=uk.bl.ethos.520902.
Full text
22
Hemmelmayr, Vera, Jean Francois Cordeau, and Teodor Gabriel Crainic. "An adaptive large neighborhood search heuristic for Two-Echelon Vehicle Routing Problems arising in city logistics." Elsevier, 2012. http://dx.doi.org/10.1016/j.cor.2012.04.007.
Full textAbstract:
In this paper,we propose an adaptive large neighborhood search heuristic for the Two-Echelon Vehicle Routing Problem (2E-VRP) and the Location Routing Problem (LRP).The 2E-VRP arises in two-level transportation systems such as those encountered in the context of city logistics. In such systems, freight arrives at a major terminal and is shipped through intermediate satellite facilities to the final
customers. The LRP can be seen as a special case of the 2E-VRP in which vehicle routing is performed only at the second level. We have developed new neighborhood search operators by exploiting the structure of the two problem classes considered and have also adapted existing operators from the literature. The operators are used in a hierarchical scheme reflecting the multi-level nature of the
problem. Computational experiments conducted on several sets of instances from the literature show that our algorithm out performs existing solution methods for the 2E-VRP and achieves excellent results on the LRP.
23
Kovàcs, Akos. "Solving the Vehicle Routing Problem with Genetic ALgorithm and Simulated Annealing." Thesis, Högskolan Dalarna, Datateknik, 2008. http://urn.kb.se/resolve?urn=urn:nbn:se:du-3306.
Full textAbstract:
This Thesis Work will concentrate on a very interesting problem, the Vehicle Routing Problem (VRP). In this problem, customers or cities have to be visited and packages have to be transported to each of them, starting from a basis point on the map. The goal is to solve the transportation problem, to be able to deliver the packages-on time for the customers,-enough package for each Customer,-using the available resources- and – of course - to be so effective as it is possible.Although this problem seems to be very easy to solve with a small number of cities or customers, it is not. In this problem the algorithm have to face with several constraints, for example opening hours, package delivery times, truck capacities, etc. This makes this problem a so called Multi Constraint Optimization Problem (MCOP). What’s more, this problem is intractable with current amount of computational power which is available for most of us. As the number of customers grow, the calculations to be done grows exponential fast, because all constraints have to be solved for each customers and it should not be forgotten that the goal is to find a solution, what is best enough, before the time for the calculation is up. This problem is introduced in the first chapter: form its basics, the Traveling Salesman Problem, using some theoretical and mathematical background it is shown, why is it so hard to optimize this problem, and although it is so hard, and there is no best algorithm known for huge number of customers, why is it a worth to deal with it. Just think about a huge transportation company with ten thousands of trucks, millions of customers: how much money could be saved if we would know the optimal path for all our packages.Although there is no best algorithm is known for this kind of optimization problems, we are trying to give an acceptable solution for it in the second and third chapter, where two algorithms are described: the Genetic Algorithm and the Simulated Annealing. Both of them are based on obtaining the processes of nature and material science. These algorithms will hardly ever be able to find the best solution for the problem, but they are able to give a very good solution in special cases within acceptable calculation time.In these chapters (2nd and 3rd) the Genetic Algorithm and Simulated Annealing is described in details, from their basis in the “real world” through their terminology and finally the basic implementation of them. The work will put a stress on the limits of these algorithms, their advantages and disadvantages, and also the comparison of them to each other.Finally, after all of these theories are shown, a simulation will be executed on an artificial environment of the VRP, with both Simulated Annealing and Genetic Algorithm. They will both solve the same problem in the same environment and are going to be compared to each other. The environment and the implementation are also described here, so as the test results obtained.Finally the possible improvements of these algorithms are discussed, and the work will try to answer the “big” question, “Which algorithm is better?”, if this question even exists.
24
Abd, Aziz Zalilah. "An investigation of the ant-based hyper-heuristic for capacitated vehicle routing problem and traveling salesman problem." Thesis, University of Nottingham, 2013. http://eprints.nottingham.ac.uk/28513/.
Full textAbstract:
A brief observation on recent research of routing problems shows that most of the methods used to tackle the problems are using heuristics and metaheuristics; and they often use problem specific knowledge to build or improve solutions. In the last few years, research on hyper-heuristic has been investigated which aims to raise the generality of optimisation systems. This thesis is concerned with the investigation of ant-based hyper-heuristic. Ant algorithms have been applied to vehicle routing problems and have produced competitive results. Therefore, it is assumed that there is a reasonable possibility that ant-based hyperheuristic could perform well for the problem. The thesis first surveys the literature for some common solution methodologies for optimisation problems and explores in some detail the ant algorithms and ant algorithm hyperheuristic methods. Furthermore, the literature specifically concerns with routing problems; the capacitated routing problem (CVRP) and the travelling salesman problem (TSP). The thesis studies the ant system algorithm and further proposes the ant algorithm hyper-heuristic, which introduces a new pheromone update rule in order to improve its performance. The proposed approach, called the ant-based hyper-heuristic is tested to two routing problems; the CVRP and TSP. Although it does not produce any best known results, the experimental results have shown that it is competitive with other methods. Most importantly, it demonstrates how simple and easy to implement low level heuristics, with no extensive parameter tuning. Further analysis shows that the approach possesses learning mechanism when compared to random hyper-heuristic. The approach investigates the number of low level heuristics appropriate and found out that the more low level heuristics used, the better solution is generated. In addition an ACO hyper-heuristic which has two categories of pheromone updates is developed. However, ant-based hyper-heuristic performs better and this is inconsistent with the performance of ACO algorithm in the literature. In TSP, we utilise two different categories of low level heuristics, the TSP heuristics and the CVRP heuristics that were previously used for the CVRP. From the observation, it can be seen that by using any heuristics for the same class of problems, ant-based hyper-heuristic is seen to be able to produce competitive results. This has demonstrated that the ant-based hyper-heuristic is a reusable method. One major advantage of this work is the usage of the same parameter for all problem instances with simple moves and swap procedures. It is hoped that in the future, results obtained will be better than current results by using better intelligent low level heuristics.
25
Simeonova, Lina. "Heuristic approaches for the vehicle routing problem with heterogeneous fleet and real life attributes." Thesis, University of Kent, 2016. https://kar.kent.ac.uk/61258/.
Full textAbstract:
The Vehicle Routing Problem with all its variants and richness is still one of the most challenging Combinatorial Optimization problems in the Management Science / Operations Research arena since its introduction in the 1950s. In this research we introduce a real life Vehicle Routing Problem, inspired by the Gas Delivery industry in the UK. It has various real life attributes which have not been researched in the past, such as demand-dependant service times, light load requirements and allowable overtime coupled with unlimited vehicle fleet. A Mixed Integer formulation of the problem is presented and the problem is solved to optimality, reporting optimal solutions and lower and upper bounds. After solving the real life routing problem, both optimally and heuristically some interesting observations and practical implications are reported, relating to better fleet utilization and better working time utilization. We design three initial solution methods, namely the Adapted Sweep, the Adapted Nearest Neighbour and the Parallel Clustering method. They are motivated by the real attributes of the Vehicle Routing Problem under research and show a very good performance in terms of reaching a good initial solution quality as compared to other famous initial solution methods in the literature. Moreover, the Adapted Sweep and the Adapted Nearest Neighbour have computational times of less than one second. Two new hybrid metaheuristic methods are designed in order to address the real life Vehicle Routing Problem. A Population Variable Neighbourhood Search with Adaptive Memory Procedure is the first method, which aims to incorporate and hybridize the learning principles of Adaptive Memory into a method which does not make use of memory structures in its original form, namely the Variable Neighbourhood Search. Moreover, we use a Population version of the Variable Neighbourhood Search in order to provide diversification to the method and to aid the learning aspect of the method. The Population Variable Neighbourhood Search with Adaptive Memory Procedure was tested extensively on the real life Vehicle Routing Problem, as well as relevant literature benchmark instances and it was found to perform well in comparison with the optimal solutions we generated. Moreover, the method shows a good performance on the benchmark instances with less than 1% deviation from the Best Known Solutions in the literature. We later extend the Population Variable Neighbourhood Search with Adaptive Memory Procedure (PVNS_AMP) and hybridize it with aspects from Tabu Search in order to create the second new hybrid metaheuristic method, namely the Population Variable Neighbourhood Search with Adaptive Memory Procedure and Tabu Search principles (TS_PVNS_AMP). The TS_PVNS_AMP was found to have better performance on the RVRP without overtime, and superior performance on the RVRP with overtime as compared to the PVNS_AMP. Moreover, the TS_PVNS_AMP showed a better performance than the PVNS_AMP on the relevant literature benchmark instances reaching Best Known Solutions in the literature with less than 0.5 % deviation from the Best Known Solutions on average. We have also tested our proposed algorithms on other VRP problems, such as the Heterogeneous Fleet VRP with imposed fleet and the School Bus Routing Problem. We have done this experimentation in order to test the generalizability of the methods and their flexibility in addressing other problems from the Vehicle Routing family. Our methodology showed good performance on the literature benchmarks for both problems in terms of solution quality and computational time, as well as a good degree of flexibility in terms of finding good heuristic solutions.
26
Václavů, Tomáš. "Optimalizace milkrunových jízd v automobilovém průmyslu." Master's thesis, Vysoká škola ekonomická v Praze, 2014. http://www.nusl.cz/ntk/nusl-193497.
Full textAbstract:
At the basic there is a connection between operation research and automotive logistics. The supply chain in this type of industry is hard to coordinate and flexibility is considered as a main key indicator. Companies increase their competitiveness through the optimization of supply chain and try to take control of every flow or a process. This idea goes throughout the departments. The main concept, which is about a connection of whole supply chain with information flow means, that there isn't need of stock and every input is highly available on time and in requested quantity and quality. This thesis describes inbound logistics and introduces some of the methods used for planning vehicle routes. In our situation which is based on car maker data set was chosen a group of a suppliers for the analysis. We used vehicle routing problem with some modifications, heuristics based on the covering problem. Founded solution was compared with the present state.
27
Mohamed, Nurum Huda binti. "Hybridisation of heuristics and exact methods for the split delivery vehicle routing problem." Thesis, University of Kent, 2012. http://ethos.bl.uk/OrderDetails.do?uin=uk.bl.ethos.591103.
Full textAbstract:
Due to the worldwide of petrol prices crises that have been rising inevitably over the past years, any reduction in the transportation cost will benefit most companies. The purpose of this research is to contribute in solving this problem by alleviating some afthis burden. This thesis is about the Split Delivery Vehicle Routing Problem (SDVRP) and some of its variants. The SDVRP is a relaxed version of the classical VRP where customers can be visited more than once. It is also applicab le to problems with customers' demands larger than the vehicle capacity. These types of split routing problems can be found app licable in many real-world logistical problems. The total cost and the number of vehicles required could be reduced by allowing split deliveries. The savings are found to be the most in those problems with customers' demands nearly as large as the vehicle capacity limit. Some constructive heuristics adapted from the savings, the sweep and the insertion methods are first put forward to solve the SDVRP. These sets of solutions are then used in several set covering-based models which are proposed to so lve the problem. Both the heuristics and the set covering-based approaches are tested on two large sets of published data set from the literature with encouraging results. Similarly on the second data set, 12 best solutions are found from the 42 instances with an average deviation of 1.37%. As split deliveries may increase customers' administration cost and inconvenience, some models to cater for this drawback are proposed and their implementations are tested and evaluated against the classical SDVRP for guidance. This thesis is organised as follows: In the first chapter, a brief overview of logistics and distribution management, in particular with respect to vehicle routing, is provided. A brief explanation about the TSP, the VRP and its variants is also presented. Methodologies for solving these kinds of problems are also given. This is then followed by an example to illustrate the benefit of sp lit deliveries in Chapter 2 together with the SDVRP mathematical formulations and a review of the methods used to tackle the SDVRP and its variants. A brief introduction to the two benchmark SDVRP data sets used is given at the end of this chapter. Several constructive heuristics are first implemented in the third chapter. These are adapted from the Savings, the Sweep and the Insertion methods to include split deliveries. These methods are coded in C++ Language and tested on the two SDVRP data sets taken from the literature and their performance is evaluated against the best published resu lts showing encouraging results. In Chapter 4, an existing mathematical programming approach based on the set covering is implemented using ILOO CPLEX Callable Library. This approach uses several sets of routes from the obtained solutions by the constructive heuristics in Chapter 3. New mathematical ILP based models are adapted and a pi lot test is conducted within a limited time to select the most appropriate model and corresponding CPLEX parameters. New best results are discovered by the selected model on the two large data sets. In Chapter 5, the dual information relating to both customers and routes, is obtained by relaxing the selected set covering-based problem as a Linear Programming. The customers' dual information is incorporated in both the classical insertion cost formula and the well-known savings formulae and is proved to be beneficial. Route reduction schemes are then designed to inc lude those promising routes only. At the end of this chapter, a new set of routes is then constructed by combining the new generated routes and those subsets of routes found previously. This set is then used in the selected model where some new best results are obtained. A new variant of the SDVRP is introduced in Chapter 6 where an incentive scheme is incorporated to overcome the inconvenience of those affected customers that have split deliveries. Two new models are then explored and adapted from the previous set covering-based models. Given that no published results exist for these variants, as a guide, those results originated from the classical SDVRP are used for comparison purpose. Our find ings and suggestions for potential future research are highlighted in the final chapter.
28
Petch, Russell Jefferson. "Constructive and population based heuristics for the vehicle routing problem with multiple trips." Thesis, University of Birmingham, 2001. http://ethos.bl.uk/OrderDetails.do?uin=uk.bl.ethos.368436.
Full text
29
Pehlivanoglu, Osman. "An Algorithm For The Capacitated Vehicle Routing Problem With Time Windows." Master's thesis, METU, 2005. http://etd.lib.metu.edu.tr/upload/2/12606657/index.pdf.
Full textAbstract:
In this thesis the capacitated vehicle routing problem with time windows (VRPTW) is studied, where the objective is to serve a set of geographically dispersed customers with known demands and predefined time windows at the minimum cost. It is hard to find an optimal solution for the VRPTW even if the problem size is small. Therefore, many heuristic methods are developed to obtain near optimal solutions. In this study a local search algorithm is proposed for solving the VRPTW, which consist of route construction and route improvement phases. Computational experiments are conducted with Solomon (1987)&rsquo<br>s and Homberger and Gehring (1999)&rsquo<br>s problem sets in order to test the performance of the proposed algorithm. From the computational results encouraging results are obtained in terms of solution quality.
30
Richter, Andreas. "Dynamische Tourenplanung - Modifikation von klassischen Heuristiken für das Dynamische Rundreiseproblem (DTSP) und das Dynamische Tourenplanungsproblem (DVRP) mit der Möglichkeit der Änderung des aktuellen Fahrzeugzuges." Doctoral thesis, Saechsische Landesbibliothek- Staats- und Universitaetsbibliothek Dresden, 2006. http://nbn-resolving.de/urn:nbn:de:swb:14-1158675300496-07673.
Full textAbstract:
Unternehmen der Transportbranche müssen gerade im operativen Tagesgeschäft bei der Tourenplanung und Transportdisposition Planungsprobleme lösen, die ein hohes Maß an Dynamik aufweisen. Speziell die Inputfaktoren der Tourenplanung sind größtenteils dynamisch und stochastisch. Aus Sicht des Autors kann die Qualität von Tourplanungsergebnissen durch die zeitnahe Berücksichtigung unvorhergesehener Ereignisse nachhaltig verbessert werden. Jedoch findet diese zunehmend erfolgskritische Funktionalität in der Literatur bisher nur unzureichend Beachtung, obwohl das Tourenplanungsproblem (Vehicle Routing Problem (VRP)) eines der wichtigsten und am meisten erforschten kombinatorischen Optimierungsprobleme ist. Verfahren für kapazitierte dynamische Tourenplanungsproblemstellungen sind in der Literatur kaum zu finden. Speziell im Bereich der Algorithmen, die eine große Lösungsgeschwindigkeit, eine leichte Verständlichkeit, eine aus praktischer Sicht akzeptable Lösungsgüte aufweisen und die Möglichkeit besitzen, die aktuellen Routenpläne der Fahrzeuge ausgehend von der momentanen geographischen Position real-time zu verändern, besteht Forschungsbedarf. Die Arbeit geht daher der Forschungsfrage nach, wie ein Verfahren für die dynamische Tourenplanung zu konstruieren ist, welches das kapazitierte dynamische Tourenplanungsproblem mit der Möglichkeit der Änderung des aktuellen Fahrzeugzuges unter Einhaltung sehr kurzer Rechenzeiten bei größtmöglicher Verständlichkeit löst. Durch die genannten Kriterien wird im Rahmen der Arbeit der Schwerpunkt auf die Modifikation von klassischen heuristischen Verfahren für die Lösung von dynamischen Tourenplanungsproblemen gelegt. Die Arbeit befasst sich sowohl mit dem Gesamtkonzept zur Disposition dynamischer Kunden als auch mit konkreten Modellen und Verfahren zur Lösung von Subproblemen innerhalb des Gesamtkonzeptes. Ferner erfolgt die Präsentation von umfangreichen Simulationsergebnissen, die auf der durchgeführten softwaretechnischen Implementierung der entwickelten Verfahren basieren. Die gute Anwendbarkeit der neuen Verfahren in der Praxis wird gezeigt. Zwecks der möglichst ganzheitlichen Betrachtung des Themengebietes erfolgt in der Arbeit zum einen sowohl die Erörterung von quantitativen als auch von qualitativen Aspekten der dynamischen Tourenplanung und zum anderen die Analyse von Schnittstellen zwischen der dynamischen Tourenplanung und eng damit verbundenen Bereichen wie Flottenmanagement oder Auftragseingang bzw. -disposition. Hierzu werden die Informationsflüsse zwischen den beteiligten Elementen im Rahmen des dynamischen Dispositionsprozesses aufgezeigt, telematische Komponenten zur Unterstützung des Informationsmanagements und der Informationsübertragung vorgestellt sowie die benötigten Inputdaten erläutert. Den Schwerpunkt der Arbeit stellt jedoch die Entwicklung von neuen quantitativen Methoden zur dynamischen Tourenplanung dar.
31
Shelbourne, Benjamin. "The vehicle routing problem with release and due dates : formulations, heuristics and lower bounds." Thesis, University of Southampton, 2016. https://eprints.soton.ac.uk/403483/.
Full textAbstract:
A novel extension of the classical vehicle routing and scheduling problem is proposed that integrates aspects of machine scheduling into vehicle routing. Associated to each customer is a release date that defines the earliest time that the order is available to leave the depot for delivery, and a due date that indicates the time by which the order should ideally be delivered to the customer. The objective is to minimise a convex combination of the operational costs and customer service level, measured as total distance travelled and total weighted tardiness, respectively. A formal definition of the problem is presented, and a variety of benchmark instances are generated to analyse the problem experimentally, and evaluate the performance of any solution approaches developed. Both experimental and theoretical contributions are made in this thesis, and these arise from the development of mixed integer linear programming(MIP) formulations, efficient heuristics, and a Dantzig-Wolfe decomposition and associated column generation algorithm. The MIP formulations extend commodity flow formulations of the capacitated vehicle routing problem, and are generally related by aggregation or disaggregation of the variables. Although a set of constraints is presented that is only valid form-commodity flow formulations. A path-relinking algorithm (PRA) is proposed that exploits the efficiency and aggressive improvement of neighbourhood search, but relies on a new path-relinking procedure and advanced population management strategies to navigate the search space effectively. To provide a comparator algorithm to the PRA, we embed the neighbourhood search into a standard iterated local search algorithm. The Dantzig-Wolfe decomposition of the problem yields a traditional set-partitioning formulation, where the pricing problem (PP) is an elementary shortest path problem with resource constraints and weighted tardiness. Two dynamic programming (DP) formulations of the PP are presented, modelling the weighted tardiness of customers in a path as a pointwise function of the release dates, or decomposing the states over the release dates. The CG algorithm relies on a multi-phase pricing algorithm that utilises DP heuristics, and a decremental state-space relaxation algorithm that solves an ng-route relaxation at each iteration. Extensive computational experiments on the benchmark instances show that the newly defined features have a significant and varied impact on the problem. As a result, finding tight lower bounds and eventually optimal solutions is highly complex, but tight upper bounds can be found efficiently using advanced heuristics.
32
Flores, Luyo Luis Ernesto. "Vehicle Routing Problem for the Collection of Information in Wireless Network." Thesis, Avignon, 2018. http://www.theses.fr/2018AVIG0230/document.
Full textAbstract:
Les progrès dans l'architecture de réseau informatique ajoutent continuellement de nouvelles fonctionnalités aux problèmes de routage des véhicules. Dans cette thèse, le problème de tournée des véhicules avec la collecte de donnée sans fil (WT-VRP) est étudié. Il recherche un itinéraire pour le véhicule chargé de collecter des informations auprès des stations ainsi qu'un planning efficace de collecte d'informations. La nouvelle fonctionnalité ajoutée ici est la possibilité de récupérer des informations via une transmission sans fil, sans visiter physiquement les stations du réseau. Le WT-VRP a des applications dans la surveillance sous-marine et la surveillance environnementale. Nous discutons les critères pour mesurer l'efficacité d'une solution et proposons des formulations de programmation linéaire en nombre entier mixte pour résoudre le problème. Des expériences computationnelles ont été réalisées pour accéder à la complexité numérique du problème et pour comparer les solutions selon les critères proposés. Ensuite, nous avons renforcé certains modèles ainsi que considéré différentes suppositions pour le réseaux sans fils. Finalement, pour être capable de résoudre le problème dans des réseaux de grande échelle, nous avons développés des méthodes heuristiques pour le WT-VRP<br>The vehicle routing problem is one of the most studied problems in Operations Research.Different variants have been treated in the past 50 years and with technologicaladvances, new challenges appear. In this thesis, we introduce a new variation of theVRP appearing in wireless networks. The new characteristic added to this well-knowproblem is the possibility of pick-up information via wireless transmissions. In the contextconsidered here, a unique base station is connected with the outside and a vehicleis responsible for collecting information via wireless connection to the vehicle when it islocated in another sufficiently close station. Simultaneous transmissions are permitted.Time of transmission depends on the distance between stations, the amount of informationtransmitted, and other physical factors (e.g obstacles along the way, installedequipment). Information to be sent outside of the network is continuously generatedin each station at a constant rate. The first contribution of this thesis is the introductionof a mixed ILP formulation for a variation in which it is only possible to send all theinformation or nothing during a wireless transmission. For this model three differentstrategies are investigated: maximizing total amount of information extracted an theend of the time horizon; maximizing the average of the information in the vehicle ateach time point; and maximizing the satisfaction of each station at the end of the timehorizon. Each strategy is translated as a different objective function for the mixed ILPformulation. The problem is then reformulated by accepting the option of sending onlypart of the information during a wireless transmission and considering only the firststrategy,(i.e. maximizing the amount of information extracted at the end of the horizontime). For this new version, we present three mixed ILP formulations, each one withadvantages and disadvantages. These mixed ILP models are compared according to theCPU time, amount of information collected, gap of unresolved instances, etc. Becausein real life we need to solve problems with a large number of stations, in this thesis,we also propose heuristics methods for the second version of the problem introduced.We build some heuristics that do not depend on the mixed ILP model (as for exampleGreedy heuristics) and also matheuristcs. In our matheuristics our best model (a vehicleevent model) is used as a base for the development of construction of Heuristics aswell as local search heuristics
33
Slavíková, Monika. "Aplikace heuristických metod v reálném rozvozním problému." Master's thesis, Vysoká škola ekonomická v Praze, 2014. http://www.nusl.cz/ntk/nusl-194501.
Full textAbstract:
This thesis is continuation of the bachelor thesis "Model of delivery routes and placement logistics centers with opportunities of their optimization". It is about distribution problems and specifically a vehicle routing problem. The aim of this thesis is finding a solution of the vehicle routing problem which will be used repeatedly in the firm. The main task is achieving the lowest costs (total kilometers) with maximum utilization of vehicle capacity; in such conditions that all requirements of logistics centers will be satisfied and maximal capacity of vehicle will be tolerated. For calculation was used a solver Gurobi 6.0.3 in system MPL for Windows 4.2, which won't, however, provide the optimal solution and problem solving takes too long time. Next for calculation was used heuristics insert method and is written by VBA (Visual Basic for Applications) in MS Excel. Finally, there is a comparison of these methods with the original solution of the vehicle routing plan and solution of the bachelor thesis. Then the computational experiment was done, which tested effect to result, if other distribution center (starting point) will be bulit. The computational experiment was consist from heuristic insert method, solver Gurobi and heuristic saving algorithm from bachelor thesis.
34
Chytrá, Alena. "Aplikace heuristických metod na rozvozní úlohu s časovými okny." Master's thesis, Vysoká škola ekonomická v Praze, 2008. http://www.nusl.cz/ntk/nusl-4504.
Full textAbstract:
This thesis demonstrates practical using of vehicle routing problem with time windows (VRPTW) and its solution by heuristic method. There are described teoretical principles of integer models, mathematical definitions of VRP with one or more vehicles, VRPTW and some heuristics for VRP. The practical part is solution of VRP by heuristic nearest neighbor. Product distribution is planed according to the firm settings in Prague. I compare existing situation and computed solution that show benefits of using described methods in conclusion.
35
Šimáně, Čestmír. "Optimalizace rozvozu léčiv ze skladu společnosti Movianto s.r.o." Master's thesis, Vysoká škola ekonomická v Praze, 2012. http://www.nusl.cz/ntk/nusl-197096.
Full textAbstract:
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.
36
Gőtz, Ondřej. "Využití metody výhodnostních čísel v úlohách kurýrní služby." Master's thesis, Vysoká škola ekonomická v Praze, 2014. http://www.nusl.cz/ntk/nusl-193489.
Full textAbstract:
The diploma thesis deals with the use of heuristic methods for solving messenger problems. The first part focuses on the proposed vehicle routing problems, especially on travelling salesman problems and the messenger problems. For individual problems are theoretically discussed mathematical models for variants with one or more vehicles and the expansion of the use of time windows and capacity constraints. The second part introduces heuristic algorithms for the method of nearest neighbour, savings method, insertion method and the exchange method on the travelling salesman problems. Then all of the mentioned algorithms are modified for use in three variants of messenger problem. First, the disposition of one vehicle, the second allows more messengers in the same starting point and the last option is more messengers at different starting points. The last part describes computational experiments and comparison of results provided by different methods. The diploma thesis includes application for solving messenger problems using savings methods programmed in Visual Basic for Application in MS Excel.
37
Richter, Andreas. "Dynamische Tourenplanung - Modifikation von klassischen Heuristiken für das Dynamische Rundreiseproblem (DTSP) und das Dynamische Tourenplanungsproblem (DVRP) mit der Möglichkeit der Änderung des aktuellen Fahrzeugzuges." Doctoral thesis, Technische Universität Dresden, 2005. https://tud.qucosa.de/id/qucosa%3A24883.
Full textAbstract:
Unternehmen der Transportbranche müssen gerade im operativen Tagesgeschäft bei der Tourenplanung und Transportdisposition Planungsprobleme lösen, die ein hohes Maß an Dynamik aufweisen. Speziell die Inputfaktoren der Tourenplanung sind größtenteils dynamisch und stochastisch. Aus Sicht des Autors kann die Qualität von Tourplanungsergebnissen durch die zeitnahe Berücksichtigung unvorhergesehener Ereignisse nachhaltig verbessert werden. Jedoch findet diese zunehmend erfolgskritische Funktionalität in der Literatur bisher nur unzureichend Beachtung, obwohl das Tourenplanungsproblem (Vehicle Routing Problem (VRP)) eines der wichtigsten und am meisten erforschten kombinatorischen Optimierungsprobleme ist. Verfahren für kapazitierte dynamische Tourenplanungsproblemstellungen sind in der Literatur kaum zu finden. Speziell im Bereich der Algorithmen, die eine große Lösungsgeschwindigkeit, eine leichte Verständlichkeit, eine aus praktischer Sicht akzeptable Lösungsgüte aufweisen und die Möglichkeit besitzen, die aktuellen Routenpläne der Fahrzeuge ausgehend von der momentanen geographischen Position real-time zu verändern, besteht Forschungsbedarf. Die Arbeit geht daher der Forschungsfrage nach, wie ein Verfahren für die dynamische Tourenplanung zu konstruieren ist, welches das kapazitierte dynamische Tourenplanungsproblem mit der Möglichkeit der Änderung des aktuellen Fahrzeugzuges unter Einhaltung sehr kurzer Rechenzeiten bei größtmöglicher Verständlichkeit löst. Durch die genannten Kriterien wird im Rahmen der Arbeit der Schwerpunkt auf die Modifikation von klassischen heuristischen Verfahren für die Lösung von dynamischen Tourenplanungsproblemen gelegt. Die Arbeit befasst sich sowohl mit dem Gesamtkonzept zur Disposition dynamischer Kunden als auch mit konkreten Modellen und Verfahren zur Lösung von Subproblemen innerhalb des Gesamtkonzeptes. Ferner erfolgt die Präsentation von umfangreichen Simulationsergebnissen, die auf der durchgeführten softwaretechnischen Implementierung der entwickelten Verfahren basieren. Die gute Anwendbarkeit der neuen Verfahren in der Praxis wird gezeigt. Zwecks der möglichst ganzheitlichen Betrachtung des Themengebietes erfolgt in der Arbeit zum einen sowohl die Erörterung von quantitativen als auch von qualitativen Aspekten der dynamischen Tourenplanung und zum anderen die Analyse von Schnittstellen zwischen der dynamischen Tourenplanung und eng damit verbundenen Bereichen wie Flottenmanagement oder Auftragseingang bzw. -disposition. Hierzu werden die Informationsflüsse zwischen den beteiligten Elementen im Rahmen des dynamischen Dispositionsprozesses aufgezeigt, telematische Komponenten zur Unterstützung des Informationsmanagements und der Informationsübertragung vorgestellt sowie die benötigten Inputdaten erläutert. Den Schwerpunkt der Arbeit stellt jedoch die Entwicklung von neuen quantitativen Methoden zur dynamischen Tourenplanung dar.
38
Vural, Arif Volkan. "The vehicle routing problem with simultaneous pick-up and deliveries and a GRASP-GA based solution heuristic." Diss., Mississippi State : Mississippi State University, 2007. http://library.msstate.edu/etd/show.asp?etd=etd-09242007-083608.
Full text
39
Conte, Francesco. "A general purpose algorithm for a class of vehicle routing problems: A benchmark analysis on literature instances." Master's thesis, Alma Mater Studiorum - Università di Bologna, 2019.
Find full textAbstract:
The aim of this work is to analyse the computational performances of a general-purpose heuristic capable of solving a large class of Vehicle Routing Problems. The general Ruin and Recreate (R&R) framework of the algorithm is discussed, with particular attention on some of the removal and insertion operators used in the implementation. The benchmark analysis is then performed using standard benchmark instances of three different routing problems.
Before analyzing the algorithm, a definition of the problem is provided together with some mathematical formulations. Exact methods are briefly discussed, whereas an exhaustive presentation of the most famous (meta)heuristic approaches is given.
The obtained results show that the algorithm returns good solutions for almost all the different problem variants with up to 500 customers.
40
Marcinko, Tomáš. "Rozvozný problém s delenou dodávkou." Master's thesis, Vysoká škola ekonomická v Praze, 2008. http://www.nusl.cz/ntk/nusl-10514.
Full textAbstract:
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.
41
Richter, Miroslav. "Rozvozní problém s dělenou dodávkou." Master's thesis, Vysoká škola ekonomická v Praze, 2009. http://www.nusl.cz/ntk/nusl-76827.
Full textAbstract:
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.
42
Nevrlý, Vlastimír. "Modely a metody pro svozové úlohy." Master's thesis, Vysoké učení technické v Brně. Fakulta strojního inženýrství, 2016. http://www.nusl.cz/ntk/nusl-242880.
Full textAbstract:
This master's thesis deals with mathematical model building for routing problems and ways to solve them. There are discussed and implemented deterministic and heuristic approaches that are suitable to be utilized. A big effort is put into building of the mathematical model describing a real world problem from the field of waste management. Appropriate algorithms are developed and modified to solve a particular problem effectively. An original graphical environment is created to illustrate acquired results and perform testing computations.
43
Holeczek, Nikolai [Verfasser], and Hans [Akademischer Betreuer] Ziegler. "The hazardous materials vehicle routing problem : literature review, risk analysis and heuristic solution procedures / Nikolai Holeczek ; Betreuer: Hans Ziegler." Passau : Universität Passau, 2021. http://d-nb.info/1234236028/34.
Full text
44
Kaja, Sai Chandana. "A New Approach for Solving the Disruption in Vehicle Routing Problem During the Delivery : A Comparative Analysis of VRP Meta-Heuristics." Thesis, Blekinge Tekniska Högskola, Institutionen för datavetenskap, 2020. http://urn.kb.se/resolve?urn=urn:nbn:se:bth-19576.
Full textAbstract:
Context. The purpose of this research paper is to describe a new approach for solving the disruption in the vehicle routing problem (DVRP) which deals with the disturbance that will occur unexpectedly within the distribution area when executing the original VRP plan. The paper then focuses further on the foremost common and usual problem in real-time scenarios i.e., vehicle-breakdown part. Therefore, the research needs to be accomplished to deal with these major disruption in routing problems in transportation. Objectives. The study first investigates to find suitable and efficient metaheuristic techniques for solving real-time vehicle routing problems than an experiment is performed with the chosen algorithms which might produce near-optimal solutions. Evaluate the performance of those selected algorithms and compare the results among each other. Methods. To answer research questions, firstly, a literature review has been performed to search out suitable meta-heuristic techniques for solving vehicle routing problems. Then based on the findings an experiment is performed to evaluate the performance of selected meta-heuristic algorithms. Results. Results from the literature review showed that the meta-heuristic approaches such as. Tabu Search, Ant Colony Optimization, and Genetic Algorithmare suitable and efficient algorithms for solving real-time vehicle routing problems. The performance of those algorithms has been calculated and compared with one another with standard benchmarks. Conclusions. The performance of a Tabu Search algorithm is best among the other algorithms, followed by Ant Colony Optimization and Genetic Algorithm. Therefore, it has been concluded that the Tabu Search is the best algorithm for solving real-time disruption problems in VRP. The results are similar to the performance comparison of the selected algorithms and standard benchmarks are presented within the research.
45
Gebauerová, Monika. "Optimalizace rozvozu pekárenských výrobků." Master's thesis, Vysoká škola ekonomická v Praze, 2010. http://www.nusl.cz/ntk/nusl-124644.
Full textAbstract:
This thesis deals with the optimization of distribution of bakery products. Firstly there are the fundamental types of vehicle routing problems and their optimization models introduced. Next part is dedicated to heuristic algorithms. The heuristic methods are introduced in general, then there are the chosen methods described. Later there are two chosen algorithms formulated. First one based on the nearest neighbour method and another one based on the savings algorithm. Both of algorithms were programmed in the Visual Basic of Applications MS Excel 2010. These algorithms were applied for the solution of the real problem dealing with the distribution of goods. The bakery company has provided the data about its customers for this purpose. The last part of this thesis is dedicated to the summary and comparison of the solution of the assigned problem that was gained by the proposed algorithms with the solution that the bakery company has put into practice.
46
Solnická, Veronika. "Návrh a aplikace heuristických metod při rozvozu objednávek zákazníkům společnosti NIKOL NÁPOJE a. s." Master's thesis, Vysoká škola ekonomická v Praze, 2010. http://www.nusl.cz/ntk/nusl-72124.
Full textAbstract:
This thesis deals with the optimization of distribution of products to consumers based on a real case study of a particular company from Opava. For this purpose, a mathematical optimization model is used to illustrate the vehicle routing problem. The study will also offer an explanation on the relevancy of heuristic methods, mainly with respect to their application in solving real life situations analogous to the one surveyed. On the basis of chosen heuristic methods (i.e. the nearest neighbour algorithm and the savings algorithm) and having taken into account the restricting conditions of the company, four algorithms were designed. These four algorithms are programmed in Visual Basic for Applications MS Excel 2007. They are aimed at solving the real problems with the distribution of ordered products that the particular company must deal with. The thesis compares the results provided by an employee of this company, and the results presented by the designed algorithms.
47
Hanek, Petr. "Implementace problému směrování vozidel pomocí algoritmu mravenčích kolonií a částicových rojů." Master's thesis, Vysoké učení technické v Brně. Fakulta elektrotechniky a komunikačních technologií, 2019. http://www.nusl.cz/ntk/nusl-400931.
Full textAbstract:
This diploma thesis focuses on meta-heuristic algorithms and their ability to solve difficult optimization problems in polynomial time. The thesis describes different kinds of meta-heuristic algorithms such as genetic algorithm, particle swarm optimization or ant colony optimization. The implemented application was written in Java and contains ant colony optimization for capacitated vehicle routing problem and particle swarm optimization which finds the best possible parameters for ant colonies.
48
Cronsioe, Carl. "Optimization of Quality in Home Care." Thesis, KTH, Optimeringslära och systemteori, 2017. http://urn.kb.se/resolve?urn=urn:nbn:se:kth:diva-209671.
Full textAbstract:
As the older population grows larger there is a growing need to provide health care at home. This services are generally done without operational research. As more people will require home care there will be a need to increase the efficiency of the service while keeping the quality high. The purpose of this thesis is to investigate how we can use operation research in home care as well as define how we can model the quality and use those quality parameters in order to offer the best possible service. The model uses VRP with Time windows in order to schedule the routes and incorporates service requirements at the customers. A solution is obtained by first constructing an initial solution that fulfills the duration constraint. Then it uses a local search with a dynamic insertion heuristic to improve on the solution. Tabu search is used as a meta-heuristic to prevent the solution the get stuck in a local minima. The solver is used in order to optimize the quality parameters. The result obtained can be used to help home care providers to determine the level of quality they can supply with a limited budget<br>När den äldre befolkningen blir större växer behovet av att tillhandahålla vård i hemmet. Denna tjänst använder i allmänhet inte systemteori. Eftersom fler människor kommer att behöva hemtjänst kommer det att finnas behov av att öka effektiviteten samtidigt som kvaliteten hålls hög. Syftet med denna avhandling är att undersöka hur vi kan använda systemteori och optimering inom hemtjänst samt definiera hur vi kan modellera kvaliteten och använda dessa kvalitetsparametrar för att erbjuda bästa möjliga service. Modellen använder VRP med Time windows för att schemalägga rutterna och inkorporerar servicebehov hos kunderna. En lösning erhålles genom att först bygga en initial lösning. Sedan använder den en lokal sökning med en dynamisk heuristisk för att förbättra lösningen. Tabu search används som en meta-heuristik för att förhindra att lösningen fastnar i lokala minima. Algoritmen används för att optimera kvalitetsparametrarna. Resultatet kan användas för att hjälpa leverantörer av hemtjänst att bestämma vilken kvalitetsnivå de kan leverera med en begränsad budget
49
Williams, Matthew J. "A Heuristic Solution to the Pickup and Delivery Problem with Applications to the Outsized Cargo Market." Ohio University / OhioLINK, 2009. http://rave.ohiolink.edu/etdc/view?acc_num=ohiou1238514369.
Full text
50
Lee, Jun-ying, and 李俊穎. "Tabu Search Heuristic for Period Vehicle Routing Problem." Thesis, 2004. http://ndltd.ncl.edu.tw/handle/fzvwh3.
Full textAbstract:
碩士<br>大同大學<br>資訊經營學系(所)<br>93<br>The Vehicle Routing Problem (VRP) under capacity and distance restrictions involves the design of minimum cost delivery routes for a fleet of vehicles, originating and terminating at a central depot, which serves a set of customers. This thesis present Tabu search algorithm for the Period Vehicle Routing Problem, the problem not only designs vehicle routes to meet required service levels for customers but also minimize distribution costs over a given several day period of time .
The VRP belongs to the class of NP-hard problems, and polynomial time algorithms for finding optimal solutions are unlikely to exist. Hence, there have been few attempts to solve it optimally among an exact algorithm based on branch and bound procedures. The branch and bound approach address small VRP adequately up to 50 customers with 8 vehicles, the approach to solve big VRP must spend the maximum of greatest time and cost. Due to limited success of exact methods, considerable attention and research effort have been devoted to the development of efficient heuristics algorithm which can provide near optimal solutions for large-sized problems in limited time. But heuristic algorithm yielding solutions whose quality often not good enough. In this thesis, applied linear programming and Savings procedure to find an initial feasible solution of PVRP, then use Tabu search to improve the One-point movement algorithm, finding improved solutions whose quality significantly surpasses that obtained by traditional heuristics.