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.

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.

Made available in DSpace on 2016-12-23T14:05:52Z (GMT). No. of bitstreams: 1 Rosemberg Silva Salles.pdf: 2088047 bytes, checksum: b650ba6ed0d06eb04f22760620fd4cc1 (MD5) Previous issue date: 2013-05-21 / This work aims to develop a procedure for collecting and physical distribution of employees by a fleet of chartered buses with the support of a geographic information system by applying the vehicle routing problem for possible optimization of routes. We begin with a review of the literature on chartered transport of employees, as well as the problems of vehicle routing and geographic information systems. Then we propose a routing procedure, which characterizes and defines the problem of collection and delivery of employees, in addition to defining the criteria for route ptimization. For this purpose, we use the software TransCAD where you do the modeling and the resolution of the problem. The procedure was applied to a case study in a large company in the Metropolitan Region of Vitória in Espírito Santo State, which provides transport their own to their employees. We generated four scenarios, analyzing the efficiency of the routes in terms of distances, travel times and operating costs. The results generated from the procedure allowed us to determine in what scenarios the routes are more efficient / Este estudo tem o objetivo de desenvolver um procedimento de coleta e distribuição física de empregados por uma frota de ônibus fretada com o apoio de um sistema de informações geográficas, aplicando o problema de roteirização de veículos para uma possível otimização das rotas. Inicialmente é feita uma revisão de literatura sobre o transporte fretado de empregados, bem como dos problemas de roteirização de veículos e dos sistemas de informações geográficas. Em seguida é proposto um procedimento de roteirização, onde se caracteriza e delimita o problema de coleta e distribuição de empregados, além de definir os critérios de otimização de rotas. Para tanto, utiliza-se o software TransCAD no qual é feita a modelagem e proposta de resolução do problema. O procedimento foi aplicado a um estudo de caso em uma empresa de grande porte na Região Metropolitana da Grande Vitória, no Estado do Espírito Santo, que oferece transporte próprio as seus empregados. Foram gerados quatro cenários, onde se analisa a eficiência das rotas em termos de distâncias, tempos de viagem e custos operacionais. Os resultados gerados a partir do procedimento permitiram determinar em que cenários as rotas se mostram mais eficientes

We define an order cutoff for a retailer as a time in the day such that orders sent to the depot before this point will be delivered by tomorrow, and orders submitted after will be delivered by the day after tomorrow. The later a retailer’s cutoff, the sooner it receives its orders which helps it to maintain ideal inventory levels. Generally, not all retailers in a supply chain can have the latest cutoff since transportation takes a significant amount of time. This thesis tries to assign optimal order cutoffs to retailers. We call this an order cutoff assignment problem and we solve it using three different mathematical programming approaches. The approaches are exhaustive route generation and selection, a series of mixed integer programs, and branch-and-price. 60 sample problems were solved and results showed that branch-and-price is often the most effective method.

We define an order cutoff for a retailer as a time in the day such that orders sent to the depot before this point will be delivered by tomorrow, and orders submitted after will be delivered by the day after tomorrow. The later a retailer’s cutoff, the sooner it receives its orders which helps it to maintain ideal inventory levels. Generally, not all retailers in a supply chain can have the latest cutoff since transportation takes a significant amount of time. This thesis tries to assign optimal order cutoffs to retailers. We call this an order cutoff assignment problem and we solve it using three different mathematical programming approaches. The approaches are exhaustive route generation and selection, a series of mixed integer programs, and branch-and-price. 60 sample problems were solved and results showed that branch-and-price is often the most effective method.

The emphasis on minimizing the logistics costs to decrease overall system costs has led the researchers to consider the interdependencies between the decisions of locating facilities and planning the routes from those facilities. The location-routing problems considering this issue are the subject of this thesis study. A two-level hierarchical distribution system is considered in which goods are delivered from the sources (plants) to the facilities (depots) and then from the facilities to the customers. The facilities are uncapacitated and operate within the shift times defined. The goods are to be delivered to the customers within their time windows by the vehicles that are capacitated. Both a mathematical model and a genetic algorithm based heuristic solution approach are proposed for this problem. We discuss the problem specific issues integrated with the general framework of the genetic algorithm applications. The computational studies are realized on a number of test problems. The results indicate that the genetic algorithm based heuristic gives satisfactory results compared with a sequential solution methodology.

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.

Thesis (Ph.D.)--Mississippi State University. Department of Industrial and Systems Engineering. / Title from title screen. Includes bibliographical references.

Στην παρούσα μεταπτυχιακή διπλωματική εργασία μελετήθηκε το πρόβλημα Δρομολόγησης Στόλου Οχημάτων με Παράθυρα Χρόνου (VRPTW) κάτω από ένα φιλικό προς το περιβάλλον πρίσμα που απαιτεί την δημιουργία ισορροπημένων και συμπαγών συστάδων. Παρουσιάζεται μια νέα ευρετική προσέγγιση που αποτελείται από τρεις φάσεις: (i) συσταδοποίηση των πελατών με συμβατά παράθυρα χρόνου, (ii) συσταδοποίηση των πελατών που βρίσκονται γεωγραφικά κοντά χρησιμοποιώντας διάφορες μεθόδους (φυσικές αποκοπές, KaHIP, τετραδικά δένδρα), (iii) μια φάση εκλέπτυνσης που είτε χωρίζει μια συστάδα σε μικρότερες, είτε συγχωνεύει συστάδες δημιουργώντας μια συμπαγή μεγαλύτερη συστάδα. Η νέα προσέγγιση αποδίδει πολύ καλά όταν χρησιμοποιείται σε δυναμικά σενάρια στα οποία ζητούνται αλλαγές στην αρχικά υπολογισμένη διαδρομή (προσθήκη μιας νέας παραγγελίας ή ακύρωση κάποιας παραγγελίας). Η νέα μέθοδος αποτελεί ένα πολύ καλό σημείο εκκίνησης για επανεξέταση και περαιτέρω βελτιστοποίηση της λύσης του προβλήματος Δρομολόγησης Στόλου Οχημάτων με Παράθυρα Χρόνου. Πειράματα που έγιναν με πραγματικά σύνολα δεδομένων δείχνουν ότι η νέα προσέγγιση υπερέχει σε σχέση με τις συνήθεις προσεγγίσεις που ξεκινούν από μία βασική λύση. / We investigate the Vehicle Routing Problem with Time Windows (VRPTW) under a new approach, consisting of three major phases: (i) a first clustering of customers with compatible time windows; (ii) a second clustering of customers with close geographic proximity based on various methods (natural cuts, KaHIP, quad trees); (iii) a refinement phase that either splits a cluster into smaller ones, or merges clusters to form a bigger compact cluster. Our approach turns out to be beneficial when used in an on-line environment, where changes to the initial tour are requested (add a new customer to the tour or drop some customers). The new method serves as a warm starting point for re-evaluating and further optimizing the solution of VRPTW. Experiments with real data sets demonstrate that our approach compares favorably with standard approaches that start from a basic (cold) solution.

We present an optimization procedure for solving the vehicle routing problem with a fixed heterogeneous fleet of vehicle. We want to minimize the passage price. We look and probe these methods: minimal element, Vogel’s Approximation and heuristic. The modeling vehicle routing problem is based on mathematical formulation. This paper present very well known problems – TSP Traveling Salesperson Problem and M-TSP. Vehicle routing problem is liked M-TSP with some specification, vehicle with a fixed carrying capacity must deliver order of goods to n customers from a single depot. Knowing the distance between customers, the problem is to find tours for the vehicles in such a way that: the total distance traveled by the vehicles is minimized, only one vehicle handles the deliveries for a given customer, the total quantity of goods that a single vehicle delivers cannot be larger than cars capacity.