To see the other types of publications on this topic, follow the link: Vehicle routing problem with loading constraints.
Dissertations / Theses on the topic 'Vehicle routing problem with loading constraints'
Create a spot-on reference in APA, MLA, Chicago, Harvard, and other styles
Consult the top 42 dissertations / theses for your research on the topic 'Vehicle routing problem with loading constraints.'
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
Koch, Henriette [Verfasser]. "Vehicle routing problems with three-dimensional loading constraints and backhauls / Henriette Koch." Magdeburg : Universitätsbibliothek, 2018. http://d-nb.info/1167856570/34.
Full text
2
Santini, Luigi Tavolaro. "Meta-heurísticas para problemas integrados de roteamento e carregamento de veículos." Universidade Nove de Julho, 2017. http://bibliotecatede.uninove.br/handle/tede/1727.
Full textAbstract:
Submitted by Nadir Basilio (nadirsb@uninove.br) on 2018-01-24T20:35:47Z
No. of bitstreams: 1
Luigi Tavolaro Santini.pdf: 2357766 bytes, checksum: b70528f7db6bf88f1285744982eb4234 (MD5)Made available in DSpace on 2018-01-24T20:35:47Z (GMT). No. of bitstreams: 1 Luigi Tavolaro Santini.pdf: 2357766 bytes, checksum: b70528f7db6bf88f1285744982eb4234 (MD5) Previous issue date: 2017-02-23
The present work deals with the Capacitated Vehicle Routing Problem with Three-Dimensional Loading Constraints. This problem is difficult to solve exactly, still relatively little studied, but important in the logistics activities of movement, warehousing and transportation. This problem consists in minimizing the total traveled distance by a homogeneous fleet of vehicles that address the issue of deliveries of customer demands, in which these demands are composed of items that have three relevant spatial dimensions. The objective of the present work is to develop heuristic and metaheuristic algorithms to solve the problem in question. The algorithms are based on the Clarke & Wright and George & Robinson heuristics, and on the Iterated Local Search and Adaptive Large Neighborhood Search metaheuristics. In the proposed algorithm, the routing problem is firstly addressed by adapting the Clarke & Wright heuristic, creating routes that are used to verify the loading pattern, thus obtaining an initial solution. In the following, an extensive search in the solution neighborhood is applied with the Iterated Local Search metaheuristic. For the best results of this search, it is checked if the loading pattern is feasible using an adapted George & Robinson algorithm. If it is not feasible, the Adaptive Large Neighborhood Search metaheuristic is executed in an attempt to find a feasible solution to the loading problem. Instances from the literature are used to evaluate the efficiency of the developed methods. The results obtained for the routing problem individually were of paramount importance to ensure the effectiveness of the Iterated Local Search metaheuristic. For the loading problem individually, the tests were also satisfactory, allowing for several feasible loading patterns using the adapted George & Robinson algorithm and the Adaptive Large Neighborhood Search metaheuristic. The results obtained with the proposed algorithm for the integrated problem were also good, being very close to those in the literature and with computational time relatively lower. As perspectives for future research, it is intended to investigate more efficient ways of exploring the solution space of the integrated problem, as well as the use of other metaheuristics.
O presente trabalho trata do Problema de Roteamento de Veículos Capacitado com Restrições de Carregamento Tridimensional. Este é um problema de difícil solução exata, ainda relativamente pouco estudado, porém importante nas atividades logísticas de movimentação, armazenagem e transporte de produtos. Este problema consiste em minimizar a distância total percorrida por uma frota homogênea de veículos que supram a questão das entregas das demandas de clientes, em que tais demandas são compostas por itens que possuem três dimensões espaciais relevantes. O objetivo do presente trabalho consiste em desenvolver algoritmos heurísticos e meta-heurísticos para resolver o problema em questão. Os algoritmos são baseados nas heurísticas de Clarke & Wright e de George & Robinson, e nas meta-heurísticas Iterated Local Search e Adaptive Large Neighborhood Search. No algoritmo proposto, primeiro trata-se o problema de roteamento adaptando-se a heurística de Clarke & Wright, criando roteiros que são utilizados para a verificação do padrão de carregamento, tendo-se assim uma solução inicial. Em seguida, é aplicada uma busca extensiva na vizinhança com a meta-heurística Iterated Local Search. Para os melhores resultados desta busca, verifica-se se o padrão de carregamento é viável utilizando o algoritmo de George & Robinson adaptado. Nos casos em que não é viável, a meta-heurística Adaptive Large Neighborhood Search é executada na tentativa de se encontrar soluções viáveis para o problema de carregamento. Instâncias da literatura são utilizadas para avaliar a eficiência dos métodos desenvolvidos. Os resultados obtidos para o problema de roteamento separadamente foram de suma importância para assegurar a eficiência do meta-heurística Iterated Local Search. Para o problema de carregamento separadamente, os testes utilizando o algoritmo de George & Robinson adaptado e a meta-heurística Adaptive Large Neighborhood Search também foram satisfatórios, permitindo a obtenção de vários padrões de carregamento factíveis. Os resultados obtidos com o algoritmo proposto para o problema integrado também foram bons, sendo bastante próximos aos da literatura e com tempo computacional relativamente menor. Como perspectivas de pesquisas futuras, pretende-se estudar formas mais eficientes de se explorar o espaço de busca do problema integrado, bem como a utilização de outras meta-heurísticas.
3
Ferreira, Kamyla Maria. "Proposta de um framework para problemas que integram decisões de localização, roteamento e empacotamento." Universidade Federal de Goiás, 2018. http://repositorio.bc.ufg.br/tede/handle/tede/8209.
Full textAbstract:
Submitted by Liliane Ferreira (ljuvencia30@gmail.com) on 2018-03-08T14:57:43Z
No. of bitstreams: 2
Dissertação - Kamyla Maria Ferreira - 2018.pdf: 2406020 bytes, checksum: 87a4f31f5a394055dd9a84a1c7c73512 (MD5)
license_rdf: 0 bytes, checksum: d41d8cd98f00b204e9800998ecf8427e (MD5)Approved for entry into archive by Luciana Ferreira (lucgeral@gmail.com) on 2018-03-12T11:16:50Z (GMT) No. of bitstreams: 2 Dissertação - Kamyla Maria Ferreira - 2018.pdf: 2406020 bytes, checksum: 87a4f31f5a394055dd9a84a1c7c73512 (MD5) license_rdf: 0 bytes, checksum: d41d8cd98f00b204e9800998ecf8427e (MD5)
Made available in DSpace on 2018-03-12T11:16:50Z (GMT). No. of bitstreams: 2 Dissertação - Kamyla Maria Ferreira - 2018.pdf: 2406020 bytes, checksum: 87a4f31f5a394055dd9a84a1c7c73512 (MD5) license_rdf: 0 bytes, checksum: d41d8cd98f00b204e9800998ecf8427e (MD5) Previous issue date: 2018-02-16
Coordenação de Aperfeiçoamento de Pessoal de Nível Superior - CAPES
This research deals with the resolution of problems that involve the location, routing, and packing decisions with focus on the location routing problem, capacitated vehicle routing problem with two-dimensional loading constraints, and location routing problem with two-dimensional loading constraints. For that, it is proposed a framework that reuses part of the algorithms, which are of a common domain, such that the development of the project is systematized. The objective of the framework is allowing the resolution of different variants of problems that integrate location, routing, and packing decisions without the need to replicate algorithms. As a proposal for an algorithm, it is developed a hybrid heuristic, which involves the cooperation between the simulated annealing and the artificial algae algorithm. The simulated annealing has four neighborhood operators, local search, and three procedures to diversify the solution. The artificial algae algorithm is combined with the skyline method in order to verify the feasibility of the two-dimensional packing constraints. Once the framework and heuristics have been codified, computational experiments are performed to test its performance, as well as comparisons are made with the most recent results published in the literature. The results show that the heuristic is competitive with other methods from the literature since it could obtain 36.25% solutions equal to the best ones reported in the literature of the location routing problem, besides the average GAP being 0.57%. For the vehicle routing problem with two-dimensional loading constraints, the heuristic could obtain 43.05% solutions equal to the best known in the literature, besides the average GAP being 3.33%. The results obtained for the location routing problem with twodimensional loading constraints were satisfactory.
Este trabalho trata da resolução de problemas que envolvem decisões de localização, roteamento e empacotamento com foco nos problemas de localização e roteamento, roteamento de veículos capacitado com restrições de empacotamento bidimensional, e localização e roteamento com restrições de empacotamento bidimensional. Para tanto, propõe-se um framework capaz de reutilizar parte dos algoritmos, que são de domínio comum, para que o desenvolvimento do projeto seja sistematizado. O objetivo é que o framework possibilite a resolução de diferentes variantes do problema que integram as decisões de localização, roteamento e empacotamento sem ter que replicar algoritmos. Como proposta de algoritmo, desenvolve-se uma heurística híbrida, a qual envolve a cooperação entre dois métodos, o recozimento simulado e o algoritmo artificial de algas. O recozimento simulado possui quatro operadores de vizinhança, procedimentos de busca local e três procedimentos para diversificar a solução. O algoritmo artificial de algas é combinado com a técnica Skyline para verificar as restrições de empacotamento bidimensional. A partir da codificação do framework e da heurística, experimentos computacionais foram realizados para testar o seu desempenho e comparar os resultados com os mais recentes da literatura. Os resultados indicam que a heurística é competitiva com os demais métodos da literatura, sendo possível obter 36,25% de soluções iguais às melhores reportadas na literatura do problema de localização e roteamento, além do GAP médio ter sido de 0,57%. No problema de roteamento de veículos com restrições de empacotamento bidimensional, a heurística obteve 43,05% soluções iguais às melhores conhecidas na literatura, além do GAP médio ter sido de 3,33%. Os resultados obtidos para o problema de localização e roteamento com restrições de empacotamento bidimensional foram satisfatórios.
4
Johar, Farhana. "Vehicle routing problem with availability constraints." Thesis, University of Southampton, 2015. https://eprints.soton.ac.uk/389516/.
Full textAbstract:
This work is concerned with solving the vehicle routing problem (VRP) which takes into account the customer's release and due date. The problem studied can also be categorized as a non-classical VRP as the departure times of vehicles depend on the dates of orders released from the production line and become available for the distribution process. Hence, the problem is known as VRP with availability constraints (VRPAC). The VRPAC is investigated through two stages. In the first stage, vehicle routing problem with release and due date (VRPRDD) is treated. At the beginning of the planning, it is assumed that the dates where the customer orders become available are known. A mathematical formulation is developed to represent the problem studied which has been solved by several heuristics, i.e. Variable Neighborhood Search (VNS), Large Neighborhood Search (LNS) and Tabu Search (TS). The algorithms are written in C++ and run on a PC computer with an Intel PentiumCore by using 56's Solomon instances with some modification. Different kinds of vehicle routing problem has been tackled in order to see the performance of proposed heuristics. The results are then compared in order to find the best method which yields the least routing cost solution. From the outcome obtained, VNS is proved to be the best algorithm which generates the least cost solution to our problem. Further investigation has been carried out in stage two which considers the extension of VRPRDD. The coordination of production sequence and vehicle routing (PS-VRPRDD) is the main subject to our problem studied in which the best production sequence will leads to the least routing. Two proposed algorithms have been used to run the test instances. The first is classical decomposition approach; Alternate which decompose the problems into two sub-problems, i.e. production sequence and vehicle routing. This will be used as benchmark to the second approach; InOneMove which take these two decisions of the sub-problems as a whole. Decision on both sub-problems is considered simultaneously as one move. The results proved that effective coordination shows the large potential savings that attract the interest of industrial distributors in optimizing their distribution process in practice.
5
Yahiaoui, Ala-Eddine. "Selective vehicle routing problem : cluster and synchronization constraints." Thesis, Compiègne, 2018. http://www.theses.fr/2018COMP2449/document.
Full textAbstract:
Le problème de tournées de véhicules (Vehicle Routing Problem - VRP) est un problème d'optimisation combinatoire utilisé généralement pour modéliser et résoudre des différents problèmes rencontrés dans les systèmes logistiques et de transport. Dans cette thèse, nous nous sommes intéressés à l'étude et la résolution d'une classe de problèmes du VRP appelée les problèmes de courses d'orientation (Team Orienteering Problem - TOP). Dans cette catégorie de problèmes, il est a priori impossible de visiter tous les clients en raison de ressources limitées. On associe plutôt un profit à chaque client qui représente sa valeur. Ce profit est collecté lorsque le client est visité par l'un des véhicules disponibles. L'objectif est donc de sélectionner un sous ensemble de clients à servir tout en maximisant le profit total collecté. Dans un premier temps, nous avons introduit une nouvelle généralisation pour le TOP que nous avons appelé le Clustered TOP ou CluTOP. Dans cette variante, les clients sont regroupés en sous-ensembles appelés clusters auxquels nous associons des profits. Pour résoudre cette variante, nous avons proposé un schéma exact basé sur l'approche des plans sécants avec des inégalités valides supplémentaires et des pré-traitements. Nous avons également conçu une méthode heuristique basée sur l'approche order first-cluster second. Cette heuristique hybride combine une heuristique de type Adaptive Large Neighborhood Search qui explore l'espace des solutions et une procédure de découpage qui explore l'espace de recherche des tours géants. De plus, la procédure de découpage est renforcée par une recherche locale afin de mieux explorer l'espace de recherche. Le deuxième problème traité dans ce travail s'appelle le Synchronized Team Orienteering Problem with Time Windows (STOPTW). Cette variante avait été initialement proposée afin de modéliser des scénarios liés à la protection des infrastructures stratégiques menacées par l'avancée des feux de forêts. En plus des contraintes de fenêtres de temps et des visites synchronisées, cette variante considère le cas d'une flotte de véhicules hétérogène. Pour résoudre ce problème, nous avons proposé une méthode heuristique basée sur l'approche GRASP×ILS qui est parvenue à dominer la seule approche existante dans la littérature. La dernière variante du TOP abordée dans cette thèse s'appelle le Set Orienteering Problem (SOP). Les clients dans cette variante sont regroupés en sous-ensembles appelés clusters. Un profit est associé à chaque groupe qui n'est obtenu que si au moins un client est desservi par le véhicule disponible. Nous avons proposé une méthode de coupes avec deux procédures de séparation pour séparer les contraintes d'élimination des sous-tours. Nous avons également proposé un algorithme Mémétique avec une procédure de découpage optimale calculée à l'aide de la programmation dynamiqueThe Vehicle Routing Problem (VRP) is a family of Combinatorial Optimization Problems generally used to solve different issues related to transportation systems and logistics. In this thesis, we focused our attention on a variant of the VRP called the Team Orienteering Problem (TOP). In this family of problems, it is a priory impossible to visit all the customers due to travel time limitation on vehicles. Instead, a profit is associated with each customer to represent its value and it is collected once the customer is visited by one of the available vehicles. The objective function is then to maximize the total collected profit with respect to the maximum travel time. Firstly, we introduced a new generalization for the TOP that we called the Clustered TOP (CluTOP). In this variant, the customers are grouped into subsets called clusters to which we associate profits. To solve this variant, we proposed an exact scheme based on the cutting plane approach with additional valid inequalities and pre-processing techniques. We also designed a heuristic method based on the order first-cluster second approach for the CluTOP. This Hybrid Heuristic combines between an ANLS heuristic that explores the solutions space and a splitting procedure that explores the giant tours search space. In addition, the splitting procedure is enhanced by local search procedure in order to enhance its coverage of search space. The second problem treated in this work is called the Synchronized Team Orienteering Problem with Time Windows (STOPTW). This variant was initially proposed in order to model scenarios related to asset protection during escaped wildfires. It considers the case of a heterogeneous fleet of vehicles along with time windows and synchronized visits. To solve this problem, we proposed a heuristic method based on the GRASP×ILS approach that led to a very outstanding results compared to the literature. The last variant of the TOP tackled in this thesis called the Set Orienteering Problem (SOP). Customers in this variant are grouped into subsets called clusters. Each cluster is associated with a profit which is gained if at least one customer is served by the single available vehicle. We proposed a Branch-and-Cut with two separation procedures to separate subtours elimination constraints. We also proposed a Memetic Algorithm with an optimal splitting procedure based on dynamic programming
6
Parolin, Erick Skorupa. "Asynchronous teams for solving the loading and routing auto-carrier problem." reponame:Repositório Institucional da UFABC, 2016.
Find full textAbstract:
Orientador: Prof. Dr. Cláudio Nogueira de MenesesDissertação (mestrado) - Universidade Federal do ABC, Programa de Pós-Graduação em Ciência da Computação, 2016.
Beyond a complex real world system composed by a set of sophisticated machines and qualied human resources distributed around manufacturing environment, the Auto In- dustry needs a little more to allow their products to reach the nal costumers. Loading vehicles like cars, trucks and vans into auto-carriers and designing routes to delivery sub- sets of vehicles to auto dealers according to their orders are relevant tasks in automotive value chain performed by transportation companies. Given the set of complex constraints related to diferent vehicle models (with diferent dimensions) to be feasibly loaded into dierent auto-carrier models plus the auto-carrier eet routing task, transportation com- panies must explore strong computational alternatives to address this optimization prob- lem. In fact, we explore in this dissertation a real world complex problem composed by two sub-problems, both belonging to NP-hard class: routing and loading. After formally dening the tackled problem, we adopt, in this dissertation, a previously studied procedure based on enumeration techniques for loading task and we propose an alternative approach employing Asynchronous Teams concept, which combines local search algorithms in order to cooperate to each other to try to resolve the routing sub-problem. Setting the results provided by our implementation of Iterated Local Search (ILS) approach (already proposed in literature for solving the routing sub-problem) as benchmark, we propose computational experiments considering real-world instances, to compare performance of ILS to ve vari- ants of our Asynchronous Teams implementations. Final results evidence the power of this proposed alternative approach for founding quality solutions and its exibility to easily assume diferent configurations.
7
Kocak, Menekse. "Vehicle Routing Problem In Cross Dockswith Shift-based Time Constraints On Products." Master's thesis, METU, 2011. http://etd.lib.metu.edu.tr/upload/12613945/index.pdf.
Full textAbstract:
In this study, the capacitated vehicle routing problem with shift based time
constraints is taken into consideration. The study stemmed from an application
in a cross dock. The considered cross dock is assumed to feed directly the
production lines of its customer. The customer has a just-in-time production
system that requires producing only in necessary quantities at the necessary
times. This necessitates the arrival of the parts/products collected from
different suppliers at the customer at the beginning of each shift of production.
The shift times constitute deadlines for the products to be collected from the
suppliers and used in each shift. The collection problem then can be seen as the
capacitated vehicle routing problem with shift based time constraints. The
objective of the collection problem is to minimize the routing costs. For the
accomplishment of this objective it is required to decide on products of which
shift(s) should be taken from a supplier when a vehicle arrives at that supplier.
For the solution of the problem a mathematical model is formulated. Since the
dealt problem is NP-Hard, meta-heuristic solution approaches based on
variable neighborhood search and simulated annealing are proposed.
Computational experimentation is conducted on the test problems which are
tailored from the capacitated vehicle routing instances from the literature.
8
El-Nashar, Ahmed. "Multi-Vehicle Dispatching and Routing with Time Window Constraints and Limited Dock Capacity." Doctoral diss., University of Central Florida, 2012. http://digital.library.ucf.edu/cdm/ref/collection/ETD/id/5197.
Full textAbstract:
The Vehicle Routing Problem with Time Windows (VRPTW) is an important and computationally hard optimization problem frequently encountered in Scheduling and logistics. The Vehicle Routing Problem (VRP) can be described as the problem of designing the most efficient and economical routes from one depot to a set of customers using a limited number of vehicles. This research addresses the VRPTW under the following additional complicating features that are often encountered in practical problems: 1. Customers have strict time windows for receiving a vehicle, i.e., vehicles are not allowed to arrive at the customer's location earlier than the lower limit of the specified time window, which is relaxed in previous research work. 2. There is a limited number of loading/unloading docks for dispatching/receiving the vehicles at the depot The main goal of this research is to propose a framework for solving the VRPTW with the constraints stated above by generating near-optimal routes for the vehicles so as to minimize the total traveling distance. First, the proposed framework clusters customers into groups based on their proximity to each other. Second, a Probabilistic Route Generation (PRG) algorithm is applied to each cluster to find the best route for visiting customers by each vehicle; multiple routes per vehicle are generated and each route is associated with a set of feasible dispatching times from the depot. Third, an assignment problem formulation determines the best dispatching time and route for each vehicle that minimizes the total traveling distance. iii The proposed algorithm is tested on a set of benchmark problems that were originally developed by Marius M. Solomon and the results indicate that the algorithm works well with about 1.14% average deviation from the best-known solutions. The benchmark problems are then modified by adjusting some of the customer time window limits, and adding the staggered vehicle dispatching constraint. For demonstration purposes, the proposed clustering and PRG algorithms are then applied to the modified benchmark problems.Ph.D.
Doctorate
Industrial Engineering and Management Systems
Engineering and Computer Science
Industrial Engineering
9
Kent, Edward. "The effects of synchronisation and other forestry commissioning constraints on vehicle routing problem solution methods." Thesis, University of Nottingham, 2016. http://ethos.bl.uk/OrderDetails.do?uin=uk.bl.ethos.716670.
Full text
10
Urbanovsky, Joshua C. "Computational Methods to Optimize High-Consequence Variants of the Vehicle Routing Problem for Relief Networks in Humanitarian Logistics." Thesis, University of North Texas, 2018. https://digital.library.unt.edu/ark:/67531/metadc1248473/.
Full textAbstract:
Optimization of relief networks in humanitarian logistics often exemplifies the need for solutions that are feasible given a hard constraint on time. For instance, the distribution of medical countermeasures immediately following a biological disaster event must be completed within a short time-frame. When these supplies are not distributed within the maximum time allowed, the severity of the disaster is quickly exacerbated. Therefore emergency response plans that fail to facilitate the transportation of these supplies in the time allowed are simply not acceptable. As a result, all optimization solutions that fail to satisfy this criterion would be deemed infeasible. This creates a conflict with the priority optimization objective in most variants of the generic vehicle routing problem (VRP). Instead of efficiently maximizing usage of vehicle resources available to construct a feasible solution, these variants ordinarily prioritize the construction of a minimum cost set of vehicle routes. Research presented in this dissertation focuses on the design and analysis of efficient computational methods for optimizing high-consequence variants of the VRP for relief networks. The conflict between prioritizing the minimization of the number of vehicles required or the minimization of total travel time is demonstrated. The optimization of the time and capacity constraints in the context of minimizing the required vehicles are independently examined. An efficient meta-heuristic algorithm based on a continuous spatial partitioning scheme is presented for constructing a minimized set of vehicle routes in practical instances of the VRP that include critically high-cost penalties. Multiple optimization priority strategies that extend this algorithm are examined and compared in a large-scale bio-emergency case study. The algorithms designed from this research are implemented and integrated into an existing computational framework that is currently used by public health officials. These computational tools enhance an emergency response planner's ability to derive a set of vehicle routes specifically optimized for the delivery of resources to dispensing facilities in the event of a bio-emergency.
11
Campos, Danilo da Silva. "Integração dos problemas de carregamento e roteamento de veículos com janela de tempo e frota heterogênea." Universidade de São Paulo, 2008. http://www.teses.usp.br/teses/disponiveis/3/3136/tde-30052008-111539/.
Full textAbstract:
Este trabalho aborda um problema ainda não explorado na literatura denominado 3L-FSMVRPTW (three-dimensional loading fleet sizing and mix vehicle routing problem with time windows), que compreende resolver simultaneamente o roteamento e carregamento tridimensional de veículos considerando frota heterogênea e janela de tempo. Foi desenvolvido um algoritmo específico para resolver o problema, denominado 3DC. Neste algoritmo foram introduzidas algumas inovações, entre elas, um novo operador de busca local (k-IntensiveSwap) e uma nova heurística de carregamento de contêiner. O algoritmo foi comparado aos melhores resultados disponíveis na literatura para problemas particulares ao apresentado. Houve bom desempenho no caso do CLP (container loading problem), bom resultado na redução do tamanho de frota no caso do 3L-VRP (threedimensional loading vehicle routing problem) e desempenho superior ao problema mais complexo estudado, o 3L-VRPTW (three-dimensional loading vehicle routing problem with time windows). Finalmente, apresentou-se um conjunto de avaliação, instâncias e soluções, para o problema completo com frota heterogênea e janela de tempo.This work presents a problem not treated yet on the literature referenced as 3L-FSMVRPTW (three-dimensional loading fleet sizing and mix vehicle routing problem with time windows), which deals simultaneously with vehicle routing and its three-dimensional loading considering heterogeneous fleet and time windows. The algorithm developed for the specific problem is called 3DC. This algorithm introduces a new local search operator called k-IntensiveSwap and a new container loading heuristic. The results are compared with the best-known results from literature for particular problems embeeded on the general problem presented. The quality of solution was good in comparison other methods for CLP (container loading problem), it has good results in terms of reduction fleet sizing in the case of 3L-VRP (three-dimensional loading vehicle routing problem) and as for 3L-VRPTW (threedimensional loading vehicle routing problem with time windows) the performance was very superior. Finally, it is presented a solution set as benchmark for future comparison with the general problem, with heterogeneous fleet.
12
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
13
Zheng, Yahong. "Supply chain management under availability & uncertainty constraints." Thesis, Ecole centrale de Lille, 2012. http://www.theses.fr/2012ECLI0019/document.
Full textAbstract:
Le management de la chaîne logistique concerne un large éventail d’activités. Nombreuses ceux qui ont un caractère incertain apportant souvent des conséquences inattendues. Malgré cela, l’incertitude est fréquemment non considérée dans la gestion de la chaîne logistique traditionnelle. En plus de l’incertitude, l’indisponibilité des ressources augmentera la complexité du problème. En prenons en compte les contraintes d’incertitude et de disponibilité nous étudions le management de la chaîne logistique selon différents aspects. Cette thèse représente une tentative de recherche afin d’aborder ce problème d’une façon systématique et complète et nous espérons que notre travail contribuera aux futurs travaux de recherche et sera utile aux gestionnaires de la chaîne logistique. Nous nous concentrons sur trois sources classiques de l’incertitude ; celle de la demande, celle la fabrication et celle liée à la distribution. Pour chaque source d’incertitude, nous analysons ses causes et ses impacts sur les performances de la chaîne logistique. L’incertitude est spécifiée dans des problèmes classiques concrets et des approches sont proposées pour les résoudre. Nous nous sommes également focalisés sur le problème bi-niveau de vendeur de journaux qui représente une chaîne logistique miniature, concerné par une double incertitude. Les méthodes utilisées offrent une bonne démonstration du traitement des variables incertaines dans les problèmes de décisionSupply chain management involves a wide range of activities. Among most of them, uncertainty exists inherently and always brings some consequence not expected. However, uncertainty is not considered much in conventional supply chain management. In the case where availability of resources is not what we expect, complexity of supply chain management increases. Taking constraints of uncertainty and availability into account, we aim to discuss supply chain management from different aspects. This thesis is an attempt of systematic and complete research from this point and we would like to offer some references to researchers and managers in supply chain. We focus on three classic sources of uncertainty: demand, manufacturing and distribution. For each source of uncertainty, we analyze its cause and its impact to the performance of the supply chain. Uncertainty is specified into concrete classic problem and an approach is proposed to solve it. Furthermore, bi-level newsboy problem as a miniature of supply chain, is focused under double uncertain environment. Treating uncertain variables is actually a treatment on operational level. The methods used offer good demonstration in treating uncertain variables in decision problems
14
Daniel, Aang. "Routing and Scheduling with Time Windows: Models and Algorithms for Tramp Sea Cargos and Rail Car-Blocks." Diss., Atlanta, Ga. : Georgia Institute of Technology, 2006. http://hdl.handle.net/1853/19698.
Full textAbstract:
Thesis (Ph.D)--Industrial and Systems Engineering, Georgia Institute of Technology, 2007.Committee Chair: Al-Khayyal, Faiz; Committee Member: Barnes, Earl; Committee Member: Johnson, Ellis; Committee Member: Karimi, IA; Committee Member: Sokol, Joel.
15
Ružička, Vladimír. "Aplikace problému Obchodního cestujícího v reálném prostředí distribuční společnosti." Master's thesis, Vysoké učení technické v Brně. Fakulta informačních technologií, 2012. http://www.nusl.cz/ntk/nusl-236578.
Full textAbstract:
This paper deals with optimal distribution issues. One may find listed problems of real life linked to distribution. Moreover, there are explained travelling salesman problem, vehicle routing problem and its variants. This work brings an overview of different ways how to solve vehicle routing problem. In practical part, there is an analysis of distribution of real company. The concept of application is presented in the second part of this paper. This concept could reduce costs of distribution in analyzed company. Testing is aimed mainly on the variant VRPCL (Vehicle Routing Problem with Continuos Loading).
16
Vega-Mejía, Carlos Alberto. "Vehicle Loading and Routing for Sustainable Transportation: Models and Algorithms." Thesis, 2018. https://vuir.vu.edu.au/39521/.
Full textAbstract:
Two of the most important supply chain activities are the planning and improvement of
the packing and distribution of products. These can be studied by means of Vehicle
Routing Problems (VRPs) and Packing Problems (PPs). Analyzing these operations
separately, and considering only economic aspects, may result in impractical solutions
and in overlooking the environmental and social aspects of distribution activities. With
the aim of addressing these issues, this thesis presents optimization models and
computational solution procedures for the Vehicle Routing Problem with Loading
Constraints (VRPLC), considering economic, environmental and social aspects (i.e. the
Triple-Bottom-Line (TBL) objectives for sustainability). It also analyzes the effect of
these aspects on routing and packing decisions.
The thesis starts with a systematic review of the PP, VRP and VRPLC literature, to
identify commonly used objective functions and constraints. These are then linked to the
three TBL dimensions. This is followed by the formulation of a VRPLC model, which
considers optimization criteria and operational constraints that have not been considered
simultaneously in previous studies. Although the model can be used to solve problems of
small size, large-sized instances can be computationally intractable and require the use of
an alternative solution method. In this regard, an efficient hybrid heuristic procedure,
which combines a Greedy Randomized Adaptive Search Procedure and a Clarke and
Wright Savings Algorithm, is developed to solve the initial model.
To specify a more relevant VRPLC application, which is efficient not only in economic
terms but in environmental and social criteria as well, these initial findings are then used
in the formulation of a VRPLC+TBL model. This extends the VRPLC model to consider
the TBL dimensions in terms of profits, fuel consumption, safety features for driving on
roads, and equitable distribution of the total payload across the vehicle fleet. Assigning
the same payload to each driver, however, may not be possible and worker dissatisfaction
may arise due to unfair workload assignments. Using the concepts of Simheuristics, the
VRPLC+TBL model is integrated with the design of incentive contracts, to provide a
mechanism to compensate workload imbalances and to further extend the social
dimension.
Overall, this thesis makes a significant contribution to the body of knowledge of routing
and loading operations by providing comprehensive models and efficient computational
solution procedures that are easy to implement. It also addresses some of the gaps
identified in the area of sustainable supply chain management related to the development
of quantitative models, heuristic methods, and the simultaneous consideration of all three
TBL dimensions. Finally, the thesis proposes some interesting ideas for further research.
17
Menezes, Gerardo Guedes Saraiva de. "A Relax-and-Fix based Approach for Solving Heterogenous Fleet Vehicle Routing Problem with Three-Dimensional Loading Constraints." Master's thesis, 2021. https://hdl.handle.net/10216/137337.
Full text
18
Levy, David. "Multiple Vehicle Routing Problem with Fuel Constraints." Thesis, 2013. http://hdl.handle.net/1969.1/151093.
Full textAbstract:
In this paper, a Multiple Vehicle Routing Problem with Fuel Constraints (MVRPFC) is considered. This problem consists of a field of targets to be visited, and a collection of vehicles with fuel tanks that may visit the targets. Consideration of this problem is mainly in the improvement of feasible solutions, but the following steps are discussed: Cost Matrix Transformation, Field Partitioning, Tour Generation and Rerouting, and Tour Improvement.
Four neighborhoods were investigated (2-opt, 3-opt, Target Vehicle Exchange, Depot Exchange), using the Variable Neighborhood Descent and Variable Neighborhood Search schemes, with APD and Voronoi partition methods. These neighborhoods were compared to investigate their performance for various instances using the above schemes and partition methods. In general, 2-opt performed as well as 3-opt in less time than 3-opt; in fact, 3-opt was the slowest of the four neighborhoods. Additionally, the Variable Neighborhood Descent scheme was found to produce better results than the Variable Neighborhood Search.
19
Côté, Jean-François. "Problèmes de tournées de véhicules avec contraintes de chargement." Thèse, 2014. http://hdl.handle.net/1866/10513.
Full textAbstract:
Cette thèse s’intéresse aux problèmes de tournées de véhicules où l’on retrouve des contraintes de chargement ayant un impact sur les séquences de livraisons permises. Plus particulièrement, les items placés dans l’espace de chargement d’un véhicule doivent être directement accessibles lors de leur livraison sans qu’il soit nécessaire de déplacer d’autres items. Ces problèmes sont rencontrés dans plusieurs entreprises de transport qui livrent de gros objets (meubles, électroménagers).
Le premier article de cette thèse porte sur une méthode exacte pour un problème de confection d’une seule tournée où un véhicule, dont l’aire de chargement est divisée en un certain nombre de piles, doit effectuer des cueillettes et des livraisons respectant une contrainte de type dernier entré, premier sorti. Lors d’une collecte, les items recueillis doivent nécessairement être déposés sur le dessus de l’une des piles. Par ailleurs, lors d’une livraison, les items doivent nécessairement se trouver sur le dessus de l’une des piles. Une méthode de séparation et évaluation avec plans sécants est proposée pour résoudre ce problème.
Le second article présente une méthode de résolution exacte, également de type séparation et évaluation avec plans sécants, pour un problème de tournées de véhicules avec chargement d’items rectangulaires en deux dimensions. L’aire de chargement des véhicules correspond aussi à un espace rectangulaire avec une orientation, puisque les items doivent être chargés et déchargés par l’un des côtés. Une contrainte impose que les items d’un client soient directement accessibles au moment de leur livraison.
Le dernier article aborde une problème de tournées de véhicules avec chargement d’items rectangulaires, mais où les dimensions de certains items ne sont pas connus avec certitude lors de la planification des tournées. Il est toutefois possible d’associer une distribution de probabilités discrète sur les dimensions possibles de ces items. Le problème est résolu de manière exacte avec la méthode L-Shape en nombres entiers.In this thesis, we study mixed vehicle routing and loading problems where a constraint is imposed on delivery sequences. More precisely, the items in the loading area of a vehicle must be directly accessible, without moving any other item, at delivery time. These problems are often found in the transportation of large objects (furniture, appliances). The first paper proposes a branch-and-cut algorithm for a variant of the single vehicle pickup and delivery problem, where the loading area of the vehicle is divided into several stacks. When an item is picked up, it must be placed on the top of one of these stacks. Conversely, an item must be on the top of one of these stacks to be delivered. This requirement is called “Last In First Out” or LIFO constraint. The second paper presents another branch-and-cut algorithm for a vehicle routing and loading problem with two-dimensional rectangular items. The loading area of the vehicles is also a rectangular area where the items are taken out from one side. A constraint states that the items of a given customer must be directly accessible at delivery time. The last paper considers a stochastic vehicle routing and loading problem with two- dimensional rectangular items where the dimensions of some items are unknown when the routes are planned. However, it is possible to associate a discrete probability distribution on the dimensions of these items. The problem is solved with the Integer L-Shaped method.
20
Côté, Jean-François. "Une heuristique à grand voisinage pour un problème de confection de tournée pour un seul véhicule avec cueillettes et livraisons et contrainte de chargement." Thèse, 2009. http://hdl.handle.net/1866/3622.
Full textAbstract:
Dans ce mémoire, nous présentons un nouveau type de problème de confection de tour- née pour un seul véhicule avec cueillettes et livraisons et contrainte de chargement. Cette variante est motivée par des problèmes similaires rapportés dans la littérature. Le véhi- cule en question contient plusieurs piles où des colis de hauteurs différentes sont empilés durant leur transport. La hauteur totale des items contenus dans chacune des piles ne peut dépasser une certaine hauteur maximale. Aucun déplacement n’est permis lors de la li- vraison d’un colis, ce qui signifie que le colis doit être sur le dessus d’une pile au moment d’être livré. De plus, tout colis i ramassé avant un colis j et contenu dans la même pile doit être livré après j. Une heuristique à grand voisinage, basé sur des travaux récents dans le domaine, est proposée comme méthode de résolution. Des résultats numériques sont rapportés pour plusieurs instances classiques ainsi que pour de nouvelles instances.In this work, we consider a new type of pickup and delivery routing problem with last- in-first-out loading constraints for a single vehicle with multiple stacks. This problem is motivated by similar problems reported in the literature. In the problem considered, items are collected and put on top of one of multiple stacks inside the vehicle, such that the total height of the items on each stack does not exceed a given threshold. The loading constraints state that if items i and j are in the same stack and item i is collected before item j, then i must be delivered after j. Furthermore, an item can be delivered only if it is on the top of a stack. An adaptive large neighborhood heuristic, based on recent studies in this field, is proposed to solve the problem. Numerical results are reported on many classical instances reported in the literature and also on some new ones.
21
Chen, Chi-Shen, and 陳契伸. "Vehicle Routing Problem with Hard/Soft Time Window Constraints." Thesis, 2001. http://ndltd.ncl.edu.tw/handle/26746509312112443878.
Full textAbstract:
碩士中原大學
工業工程研究所
89
This research proposes a heuristic, Tabu-Threshold Algorithm (TTA), to efficiently and effectively solve Vehicle Routing Problem with Hard/Soft Time Window Constraints (VRPHTW / VRPSTW). TTA integrates Tabu Search (TS) and Threshold Accepting (TA), two of the most popular generic heuristics in solving VRPHTW in recent years. The first objective is to determine the route that minimizes the total vehicle travel distances. This, in turn, leads to quick response to customer demands. The second objective is to find the minimum required number of vehicles. This, in turn, results in low transportation cost. Solomon’s 56 benchmark instances were tested for TTA. TTA consists of three phases: initial solution construction, local search improvement, and generic search improvement. In the initial solution construction phase, Enhanced Savings Method and Nearest Neighbor Method are used. In the local search improvement phase, vehicles reduction and neighborhood search modules are proposed. In the generic search improvement phase, a hybrid algorithm of TS and TA is used to improve the initial solution. TTA is coded in Visual Basic 6.0 and evaluated at a PentiumⅢ550 PC. TTA results in good solution quality and efficiency. The average deviation of distance is less than 5% and the average deviation of vehicle numbers is about 8%, compared to the known “best” solutions. The average computation time is approximately 5 minutes to solve all the instances.
22
Wei, Zong-Che, and 魏宗徹. "The Vehicle Routing Problem With Backhaul and Time Window Constraints." Thesis, 2001. http://ndltd.ncl.edu.tw/handle/35707804237946650508.
Full textAbstract:
碩士元智大學
工業工程研究所
89
The transportation cost accounts for a large amount in logistics system, hence how to design a useful vehicle routing rule can reduce the transportation cost and increase the profit is the primary issues for the company. Ordinary Vehicle Routing Problem with Backhaul（VRPB）assumes that the pickup operations are followed by delivery. The operations are either simple delivery or pickup, and single vehicle type is assumed. The purpose of this study was to allow the priority flexibility of pickup and delivery via pickup allowance rate. Where the delivery goods was over the specified percents of carrying capacity, this vehicle could break the priority of delivery and then made both delivery and pickup operation at the customer station. However, both delivery and pickup operation could not exceed the vehicle capacity constraint. Customers were classified by 3 subgroups, one for delivery（or linehaul）, one for pickup（or backhaul）and the other is the mix of linehaul and backhaul. We also study the imparts of both single type and mixed type vehicle on the solution. A genetic algorithm was applied to the problem and parameters were determined by Taguchi Method for optimal design. The test problem by Solomon were tested to check the feasibility of the approach. The results show that the minimize total cost occurred at the level of pickup customers is 50% and percent of pickup allowance is 10%. The mix vehicle consideration performs better is total cost（-19.5%）and average utilization（+14.4%）.
23
蔡佳君. "The Variable-Capacity Vehicle Routing Problem With Time Window Constraints." Thesis, 2001. http://ndltd.ncl.edu.tw/handle/45262786077175990175.
Full text
24
Lin, Shi-An, and 林士安. "Incorporating Cargo Loading Feasibility into a B2B Delivery Vehicle Routing Problem." Thesis, 2019. http://ndltd.ncl.edu.tw/handle/563q7v.
Full textAbstract:
碩士國立東華大學
運籌管理研究所
107
In the supply chain management, the cost of transporting the cargo was account for a large part in the operation process. The efficiency distribution planning not only can save the cost, but also to increase the customer satisfaction. However, distribution planning was much difficult in practice, especially in the loading problem. Three dimensional loading is an NP-hard problem. In the logistics company, they always face to a plight that they cannot load cargos into a specific vehicle completely, so that the workers have to reload again or use extra vehicle. In the past, we just consider the limit of weight or capacity of vehicle in CVRP problem, the results were hard to be executed in the real situation, and probably increased the extra operation cost and time. The main idea of this paper was to solve the 3L-CVRP problem by the proposed heuristics algorithms, based on “Routing first- Packing second” strategy. We used simulated annealing algorithm to find an initial solution of the improved CVRP problem and solve the loading problem based on CargoWiz software. The object was to minimize the number of vehicle used. And we took the real data of a B2B (Business to Business) logistics company for instance in this paper, that was rarely seem in before. The characteristics of B2B cargos were a wide variety and the qualities were so much different. Eventually, we found feasible solutions by the methods we proposed. The logistics company can follow our methods to make a distribution plan in advance to avoid the loading infeasibility.
25
Tseng, Wei-Hao, and 曾維豪. "The Vehicle Routing Problem with Soft Time Window and Backhaul Constraints." Thesis, 2000. http://ndltd.ncl.edu.tw/handle/41039945391253313996.
Full textAbstract:
碩士元智大學
工業工程研究所
88
This article describes a tabu search heuristic for the vehicle routing problem with backhaul and time window (VRPBTW). The vehicle routing problem with backhaul (VRPB) is the extension of the classical vehicle routing problem (VRP). The VRP only considers the delivery of customers to the stations. However, for the VRPB, the set of customers is partitioned into two subsets : linehaul customers where a given quantity of goods is delivered from a central depot, and backhaul customers where a given quantity of goods is collected from a backhaul customer and transported to the depot. To the VRPB problem, the backhaul must be served after the linehaul on each route. This constraint arises because it is often inconvenient to rearrange linehaul loads onboard in order to accommodate new pick-up loads, and linehaul are generally with higher priority stops than backhauls. If we arrange the load depend on route sequence and the load have time window constraint, this constraint will be relaxed. This study is to relax this constraint and find out its feasibility. We utilize pick-up allowance rate (PAR) to forbid the front of route which can’t be backhauled. Furthermore, the time of beginning of service at each customer must occur within a particular time interval. We utilized tabu search heuristic coupled with three initial solution and three exchange methods to solve the VRPB. Taquchi method was also utilized to find the best design parameters. Computational results are reported on standard set of test problems. The results shows that the use of PAR can reduce the route cost and number of vehicle.
26
Cheng, Pefo, and 張寶豐. "A Hybrid Heuristic for Vehicle Routing Problem with Time Window Constraints." Thesis, 2003. http://ndltd.ncl.edu.tw/handle/01881213204828485657.
Full textAbstract:
碩士中原大學
工業工程研究所
91
This research proposes a heuristic, Enhanced Tabu - Perturbation Algorithm (ETPA), to efficiently and effectively solve Vehicle Routing Problem with Time Window Constraints (VRPTW). ETPA integrates Tabu Search (TS), Noising Method (NM) and Flip Flop Method (FF). TS is one of the most popular generic heuristics in solving VRPHTW in recent years. FF and NM are combinatorial optimization meta-heuristics. The first objective is to determine the route that minimizes the total vehicle travel distances. This leads to quick response to satisfy customer demands. The second objective is to find the minimum required number of vehicles. This can reduce the transportation cost. Solomon’s 56 benchmark instances were tested for ETPA. ETPA consists of three phases: initial solution construction, local search improvement, and generic search improvement. In the initial solution construction phase, Enhanced Nearest Neighbor Method is used. In the local search improvement phase, vehicles reduction and Neighborhood Search modules are proposed. In the generic search improvement phase, a hybrid algorithm integrating TS, NM and FF is used to improve the initial solution. ETPA results in good solution quality and efficiency. The average deviation of distance is less than 3.9% and the average deviation of number of vehicles is about 9.5%, compared to the known “best” solutions. The average computation time is approximately 15 minutes to solve an instance.
27
YEH, YU-FAN, and 葉育帆. "The vehicle routing problem with soft time window and capacitated constraints." Thesis, 2019. http://ndltd.ncl.edu.tw/handle/4g2me6.
Full textAbstract:
碩士國立勤益科技大學
工業工程與管理系
107
Logistics distribution have become the key conditions for the interconnection of various industries. In the rapid development of Internet, technology and transportation, how to improve the global competitive advantage of their enterprises, provide customers with instant logistics system, ordering to receiving in one day, so how can decision makers quickly choose the logistics distribution route to save transportation time, vehicle cost and reduce vehicle fuel consumption, so as to avoid unnecessary waste, it is already considered as a decision maker, so this study explored the topic of transportation problems. In order to better conform to the actual case, this study will consider the vehicle routing problem with soft time windows (VRPSTW), let each customer's business hours be variable, and then restrict the consistency of each vehicle type, the same vehicle loading limitation, the same vehicle distance limitation, the same total vehicle service time, avoid problems such as employees overtime and excess workloads, make the problems closer to the current industry through the above restrictions, and the goal of minimizing the total cost is calculated. The total cost is divided into four parts: distance cost, vehicle fixed cost, vehicle early arrival cost, and vehicle late cost. The four costs are firstly formulated mathematical mixed integer programming model, and using LINGO 10.0 to solve the problem to get the best answer solution, and then using the genetic algorithm to solve the problem with MATLAB to find the approximate optimal solution, and save time and improve efficiency. This study assumes three cases to verify the proposed MIP model and enhanced genetic algorithm. After comparison, it is found that the results in Case 1 and Case 2 are the same, while the results in Case 3 are inconsistent, but the error rate is only 8.68%. This method can effectively solve the solution and get the approximate optimal solution to replace the MIP model.
28
Wang, Mu-Kung, and 王木坤. "A Study of The Vehicle Routing and Scheduling Problem Under Time Constraints." Thesis, 1997. http://ndltd.ncl.edu.tw/handle/15312587805680675058.
Full textAbstract:
碩士中原大學
工業工程學系
85
Different from other businesses, the distribution center spends a lot on transportation cost. However, it is an important whether the distribution center gets increasement to reduce its transportation cost. In the past, the distribution center only considers the routing and vehicle scheduling problem for the transportation cost; Now, "Customers Are Always Right", One often claims to receive his demand on the special time interval; if not, One will refuse the service or will fine the distribution center, we call this "Time Windows Constraints". The transportation model becomes more complex with the constraint and hard to solve it. On the considerations of vehicle routing and time windows constraints, this research proposed three algorithms to reduce the transportation cost. Both "Minimize cost with equal-time interval" and "Minimize cost with fix three-points" do the routing first, then scheduling. The different between the two algorithm is that, the former decides the vehicle''s departure time for the first customer with the minimum cost, the latter consider minimum cost for every two customers, the "Minimum cost with group technology" will gather all customers into appropriate groups by their time window''s midpoint, then scheduling by one of the first two algorithms with the lower costs. Finally, this research will propose a algorithm simultaneously considering the distance and time windows based on the "Minimum cost with group technology", and compre the four algorithm with the point of view for the cost and distance. At the end of this research, we develop a new algorithm based on "Minimum cost with group technology", which both consider the routing and the scheduling. We call it "Minimum cost with dynamic group technology", and compare its performance with the other algorithms.
29
Luo, Youh Wen, and 羅毓文. "Exact and Approximate Approaches for the Vehicle Routing Problem with Packing Constraints." Thesis, 1995. http://ndltd.ncl.edu.tw/handle/31673209223814430399.
Full text
30
Chen, Bai-Jie, and 陳百傑. "A Meta-Heuristic Method for Vehicle Routing Problem with Time Window Constraints." Thesis, 2002. http://ndltd.ncl.edu.tw/handle/21993520915168074947.
Full textAbstract:
碩士中原大學
工業工程研究所
90
ABSTRACT This research proposes a heuristic, Tabu-Disturbance Algorithm (TDA), to efficiently and effectively solve Vehicle Routing Problem with Time Window Constraints (VRPTW). TDA integrates Tabu Search (TS) and Noising Method (NM). TS is the most popular generic heuristic in solving VRPHTW in recent years and NM is a combinatorial optimization meta-heuristic. The first objective is to determine the route that minimizes the total vehicle travel distances. This leads to quick response to satisfy customer demands. The second objective is to find the minimum required number of vehicles. This can reduce the transportation cost. Solomon’s 56 benchmark instances were tested for TDA. TDA consists of three phases: initial solution construction, local search improvement, and disturbed search improvement. In the initial solution construction phase, enhanced Nearest Neighbor Method is used. In the local search improvement phase, vehicles reduction and Neighborhood Search modules are proposed. In the disturbed search improvement phase, a hybrid algorithm of TS and NM is used to improve the initial solution. TDA results in good solution quality and efficiency. The average deviation of distance is less than 3% and the average deviation of number of vehicles is about 9.5%, compared to the known “best” solutions. The average computation time is approximately 8 minutes to solve an instance.
31
Grebennik, I., O. Lytvynenko, O. Baranov, and R. Dupas. "Three-dimensional one-to-one pickup and delivery routing problem with loading constraints." Thesis, 2016. http://openarchive.nure.ua/handle/document/3806.
Full textAbstract:
We propose mathematical model and solving strategy for PDP
with 3D loading constraints in terms of combinatorial configuration instead of
traditional approach that uses boolean variables. We solve traditional one-to-one Pickup and Delivery Problem in combination with problem of packing delivered items into vehicles by means of proposed combinatorial generation
algorithm.
32
Chou, Bo-Yan, and 周柏諺. "Three-Dimensional Container Loading and Vehicle Routing Problem with General Overlapping Service Regions." Thesis, 2019. http://ndltd.ncl.edu.tw/handle/222uhr.
Full textAbstract:
碩士國立交通大學
運輸與物流管理學系
107
This study investigates the Three-Dimensional Container Loading and Capacitated Vehicle Routing Problem with general overlapping service regions, which is an extension of the three-dimensional capacitated vehicle routing problem (3L-CVRP). We are interested in solving the optimal decisions including the fleet deployment using the vehicles in the original region, the trans-regional vehicles and the vehicles from outsourcing, the corresponding vehicle routes for logistics companies to satisfy customers’ demand, and the three-dimensional container loading with pre-determined and overlapping service regions. We take a districting concept of “general overlapping service regions” (GOSR) into consideration in this study, which would increase the flexibility in vehicle routing and fleet deployment, and help reducing the operating cost of the distribution operations for logistics companies. We formulate a mathematical model following the scenario of the 3L-CVRP with overlapping service regions. It is well known that the conventional VRP is NP-hard. Since the concerned problem in this study is more complicated than the conventional VRP, it will be more difficult to solve. Consequently, we propose a genetic algorithm (GA) as our solution approach. The data structure of chromosome encoding in our GA is not only comprehensive, but also easy to deal with the situation of GOSR and to understand cargo assignment and three-dimensional cargo loading situation. We randomly generate our instances in our numerical experiments by referring to the benchmark problems for the conventional VRP and 3L-CVRP, taking into account of the characteristics of GOSR. Our experimental results show that our proposed GA is able to obtain solutions with excellently quality effectively, and making use of GOSR may save significant distribution operating cost for logistics companies.
33
Tsai, Yu-Jing, and 蔡玉晶. "A Meta-Heuristic Method for Vehicle Routing Problem with Hard Time Window Constraints." Thesis, 2004. http://ndltd.ncl.edu.tw/handle/06187522153149675757.
Full textAbstract:
碩士中原大學
工業工程研究所
92
This research proposes a heuristic, Tabu-Threshold Genetic Algorithm (TTGA), to efficiently and effectively solve Vehicle Routing Problem with Hard Time Window Constraints (VRPHTW). TTGA integrates Tabu Search (TS), Threshold Accepting (TA) and Genetic Algorithms (GAs) that are the most popular generic heuristic in solving VRPHTW in recent years. The first objective is to determine the routes that minimize the total vehicle travel distances, and the second objective is to find the minimum required number of vehicles. Both objectives lead to quick response to satisfy customer demands and reduce the transportation cost. TTGA consists of three phases: initial solution construction, local search improvement, and generic search improvement. In the initial solution construction phase, enhanced Nearest Neighbor Method is used. In the local search improvement phase, vehicles reduction and Neighborhood Search modules are proposed. In the generic search improvement phase, a hybrid algorithm of TS, TA and GA is used to improve the current solution. TTGA results in good solution quality and efficiency. The average deviation of distance is less than 3.6% and the average deviation of the number of vehicles is about 11.5%, compared to the best known solutions of Solomon’s 56 benchmark instances.
34
Alves, Cindy dos Santos. "Vehicle Routing Problem with multiple trips and time constraints (VRPMTTC): A Case Study." Master's thesis, 2020. https://hdl.handle.net/10216/132487.
Full text
35
Alves, Cindy dos Santos. "Vehicle Routing Problem with multiple trips and time constraints (VRPMTTC): A Case Study." Dissertação, 2020. https://hdl.handle.net/10216/132487.
Full text
36
Ao, Chun-Wei, and 敖君瑋. "A Tabu Search Heuristic for the Vehicle Routing Problem with Soft Time Window Constraints." Thesis, 1999. http://ndltd.ncl.edu.tw/handle/55834049259274480226.
Full textAbstract:
碩士元智大學
工業工程研究所
87
The distribution center has to make optimal daily vehicle routing decisions to satisfy the customers’ demands and search for the reasonable transportation cost during the business flow process. Previous vehicle routing problem with time windows (VRPTW) only considers the vehicle capacity, total available time and customer’s time window constraints, and the search for the best vehicle routing decisions is based on the minimum transportation cost. However, as the traffic flow grows, the on-time delivery is getting difficult to achieve under the time constraints. Hence, the vehicle routing problem with soft time windows (VRPSTW) emerges as the penalty cost approach substitutes the reject acceptance, which violates the time window constraints. This study dealt with the VRPSTW, and utilized nearest-neighbor, sweep, and saving methods to find the initial solution. Then, the tabu search rules were utilized to improve the initial solutions. The approach was tested by the data sets of Solomon’s (1987) vehicle routing problem. The results show that the use of nearest-neighbor method as initial solution performs best in getting the best improved solutions. This approach also performs best in data sets of R2 and RC2 then previous solution.
37
羅敏華. "A new ant colony algorithm to vehicle routing problem under capacity and distance constraints." Thesis, 2003. http://ndltd.ncl.edu.tw/handle/34262488315574872502.
Full text
38
Kuo-HsiangChang and 張國祥. "A Hybrid Evolutionary Search Strategy for the Vehicle Routing Problem with Time Window Constraints." Thesis, 2012. http://ndltd.ncl.edu.tw/handle/22827306750471821394.
Full textAbstract:
碩士國立成功大學
電機工程學系專班
100
The vehicle routing problem with time windows (VRPTW) involves the routing of a set of vehicles with finite capacity from a depot to a set of geographically scattered nodes with known demands and predefined time windows. This problem is solved by optimizing routes for the vehicles so as to meet all given constraints as well as to minimize the objectives of number of vehicles and delivering distance. This thesis proposes a hybrid evolutionary search strategy algorithm (HESSA) that incorporates heuristics solution of the local exploration in the evolutionary search with specialized genetic operators. The fitness function and mutation of the sequence-oriented optimization in VRPTW are realized by the inverse of the total distance and the roulette wheel, respectively. Different existing VRPTW researches often aggregate multiple criteria and constraints into a compromise function, the proposed HESSA simultaneously optimizes all routing constraints and objectives, and improves the routing solutions in many appearances, such as lower routing cost, better cluster trace, and wider scattering area search. The HESSA can obtain the optimal solution by balancing the exploring and developing ability. Finally, the proposed HESSA is applied to solve the benchmark problem, Solomon’s 56 VRPTW 100-customer instances. Simulation results demonstrate that 17 routing solutions are better than or competitive as compared to the best solutions published in the literature.
39
Moolman, A. J. (Alwyn Jakobus). "Design and implementation of an integrated algorithm for the vehicle routing problem with multiple constraints." Diss., 2004. http://hdl.handle.net/2263/25036.
Full text
40
Moolman, A. J. (Alwyn Jakobus). "Design of a selective parallel heuristic algorithm for the vehicle routing problem on an adaptive object model." Thesis, 2010. http://hdl.handle.net/2263/29598.
Full textAbstract:
The Vehicle Routing Problem has been around for more than 50 years and has been of major interest to the operations research community. The VRP pose a complex problem with major benefits for the industry. In every supply chain transportation occurs between customers and suppliers. In this thesis, we analyze the use of a multiple pheromone trial in using Ant Systems to solve the VRP. The goal is to find a reasonable solution for data environments of derivatives of the basic VRP. An adaptive object model approach is followed to allow for additional constraints and customizable cost functions. A parallel method is used to improve speed and traversing the solution space. The Ant System is applied to the local search operations as well as the data objects. The Tabu Search method is used in the local search part of the solution. The study succeeds in allowing for all of the key performance indicators, i.e. efficiency, effectiveness, alignment, agility and integration for an IT system, where the traditional research on a VRP algorithm only focuses on the first two.Thesis (PhD)--University of Pretoria, 2010.
Industrial and Systems Engineering
unrestricted
41
"Logistical Planning of Mobile Food Retailers Operating Within Urban Food Desert Environments." Doctoral diss., 2016. http://hdl.handle.net/2286/R.I.40708.
Full textAbstract:
abstract: Mobile healthy food retailers are a novel alleviation technique to address disparities in access to urban produce stores in food desert communities. Such retailers, which tend to exclusively stock produce items, have become significantly more popular in the past decade, but many are unable to achieve economic sustainability. Therefore, when local and federal grants and scholarships are no longer available for a mobile food retailer, they must stop operating which poses serious health risks to consumers who rely on their services.
To address these issues, a framework was established in this dissertation to aid mobile food retailers with reaching economic sustainability by addressing two key operational decisions. The first decision was the stocked product mix of the mobile retailer. In this problem, it was assumed that mobile retailers want to balance the health, consumer cost, and retailer profitability of their product mix. The second investigated decision was the scheduling and routing plan of the mobile retailer. In this problem, it was assumed that mobile retailers operate similarly to traditional distribution vehicles with the exception that their customers are willing to travel between service locations so long as they are in close proximity.
For each of these problems, multiple formulations were developed which address many of the nuances for most existing mobile food retailers. For each problem, a combination of exact and heuristic solution procedures were developed with many utilizing software independent methodologies as it was assumed that mobile retailers would not have access to advanced computational software. Extensive computational tests were performed on these algorithm with the findings demonstrating the advantages of the developed procedures over other algorithms and commercial software.
The applicability of these techniques to mobile food retailers was demonstrated through a case study on a local Phoenix, AZ mobile retailer. Both the product mix and routing of the retailer were evaluated using the developed tools under a variety of conditions and assumptions. The results from this study clearly demonstrate that improved decision making can result in improved profits and longitudinal sustainability for the Phoenix mobile food retailer and similar entities.Dissertation/Thesis
Doctoral Dissertation Industrial Engineering 2016
42
Dayarian, Iman. "Tactical Vehicle Routing Planning with Application to Milk Collection and Distribution." Thèse, 2013. http://hdl.handle.net/1866/10802.
Full textAbstract:
De nombreux problèmes pratiques qui se posent dans dans le domaine de la logistique, peuvent être modélisés comme des problèmes de tournées de véhicules. De façon générale, cette famille de problèmes implique la conception de routes, débutant et se terminant à un dépôt, qui sont utilisées pour distribuer des biens à un nombre de clients géographiquement dispersé dans un contexte où les coûts associés aux routes sont minimisés. Selon le type de problème, un ou plusieurs dépôts peuvent-être présents. Les problèmes de tournées de véhicules sont parmi les problèmes combinatoires les plus difficiles à résoudre.
Dans cette thèse, nous étudions un problème d’optimisation combinatoire, appartenant aux classes des problèmes de tournées de véhicules, qui est liée au contexte des réseaux de transport. Nous introduisons un nouveau problème qui est principalement inspiré des activités de collecte de lait des fermes de production, et de la redistribution du produit collecté aux usines de transformation, pour la province de Québec. Deux variantes de ce problème sont considérées. La première, vise la conception d’un plan tactique de routage pour le problème de la collecte-redistribution de lait sur un horizon donné, en supposant que le niveau de la production au cours de l’horizon est fixé. La deuxième variante, vise à fournir un plan plus précis en tenant compte de la variation potentielle de niveau de production pouvant survenir au cours de l’horizon considéré.
Dans la première partie de cette thèse, nous décrivons un algorithme exact pour la première variante du problème qui se caractérise par la présence de fenêtres de temps, plusieurs dépôts, et une flotte hétérogène de véhicules, et dont l’objectif est de minimiser le coût de routage. À cette fin, le problème est modélisé comme un problème multi-attributs de tournées de véhicules. L’algorithme exact est basé sur la génération de colonnes impliquant un algorithme de plus court chemin élémentaire avec contraintes de ressources.
Dans la deuxième partie, nous concevons un algorithme exact pour résoudre la deuxième variante du problème. À cette fin, le problème est modélisé comme un problème de tournées de véhicules multi-périodes prenant en compte explicitement les variations potentielles du niveau de production sur un horizon donné. De nouvelles stratégies sont proposées pour résoudre le problème de plus court chemin élémentaire avec contraintes de ressources, impliquant dans ce cas une structure particulière étant donné la caractéristique multi-périodes du problème général. Pour résoudre des instances de taille réaliste dans des temps de calcul raisonnables, une approche de résolution de nature heuristique est requise. La troisième partie propose un algorithme de recherche adaptative à grands voisinages où de nombreuses nouvelles stratégies d’exploration et d’exploitation sont proposées pour améliorer la performances de l’algorithme proposé en termes de la qualité de la solution obtenue et du temps de calcul nécessaire.Many practical problems arising in real-world applications in the field of logistics can be modeled as vehicle routing problems (VRP). In broad terms, VRPs deal with designing optimal routes for delivering goods or services to a number of geographically scattered customers in a context in which, routing costs are minimized. Depending on the type of problem, one or several depots may be present. Routing problems are among the most difficult combinatorial optimization problems. In this dissertation we study a special combinatorial optimization problem, belonging to the class of the vehicle routing problem that is strongly linked to the context of the transportation networks. We introduce a new problem setting, which is mainly inspired by the activities of collecting milk from production farms and distributing the collected product to processing plants in Quebec. Two different variants of this problem setting are considered. The first variant seeks a tactical routing plan for the milk collection-distribution problem over a given planning horizon assuming that the production level over the considered horizon is fixed. The second variant aims to provide a more accurate plan by taking into account potential variations in terms of production level, which may occur during the course of a horizon. This thesis is cast into three main parts, as follows: In the first part, we describe an exact algorithm for the first variant of the problem, which is characterized by the presence of time windows, multiple depots, and a heterogeneous fleet of vehicles, where the objective is to minimize the routing cost. To this end, the problem is modeled as a multi-attribute vehicle routing problem. The exact algorithm proposed is based on the column generation approach, coupled with an elementary shortest path algorithm with resource constraints. In the second part, we design an exact framework to address the second variant of the problem. To this end, the problem is modeled as a multi-period vehicle routing problem, which explicitly takes into account potential production level variations over a horizon. New strategies are proposed to tackle the particular structure of the multi-period elementary shortest path algorithm with resource constraints. To solve realistic instances of the second variant of the problem in reasonable computation times, a heuristic approach is required. In the third part of this thesis, we propose an adaptive large neighborhood search, where various new exploration and exploitation strategies are proposed to improve the performance of the algorithm in terms of solution quality and computational efficiency.