The following work concerns the study of the evolutionary algorithm, which optimizes freight transport planning. The demand for freight transport is constantly increasing nowadays and with creating, implementing and using proper route planning we are able to significantly reduce transportation costs. However, it is preferably to implement it in companies with large numbers of served customers and with a sufficiently large fleet of vehicles.   The study starts by defining what fright transport planning problem is and by characterizing its existing specifications and variants. My work proceeds to give a background of the possible solutions to the multifaceted aspects of the problem. The specific subproblem I choose to focus on is the Vehicle routing problem with Pickup and Delivery for which I apply the optimization solution. In the main body of my thesis, I will elaborate on the chosen optimization solution which encompasses the genetic algorithm and evolutionary strategy. The aim of the study is to measure the suitability of the algorithms and techniques used, for which reason the final part of my work will deal with the analysis and evaluation of the experiments.

This thesis deals with portation of the OptaPlanner tool to the Android operating system. The OptaPlanner is used for solving planning problems and it is completely written in the Java programming language which is also used for application development of the Android operating system. However, Android does not contain all of the Java Standard Edition Application Programming Interface libraries and porting of OptaPlanner to Android thus causes dependency problems. The result of the thesis is solution design and implementation of the problems mentioned above and model Android Vehicle Routing Problem application which uses ported OptaPlanner tool.

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.

El presente estudio versa sobre la ejecución proyectos eléctricos en baja tensión, los cuales son ejecutados por una empresa de servicios cuyas operaciones se realizan en Lima. El capítulo 1 presenta la literatura asociada a la solución del problema, en donde se desarrolla el marco teórico de las metodologías propuestas. El capítulo 2 muestra el uso de las herramientas de la ingeniería industrial a efectos de identificar el problema: “retrasos en la ejecución de proyectos de baja tensión con reforma”. Esta problemática genera una pérdida anual de 381 miles de soles y un déficit de capital de trabajo de 11,500 miles de soles correspondiente al año 2017. El capítulo 3 plantea la solución de la problemática expuesta, para lo cual se definen dos etapas. La primera permite la eliminación del backlog acumulado hasta el mes de setiembre de 2018. La segunda se refiere al desarrollo de las metodologías: Last Planner System, Vehicle Routing Problem y Workforce Management. En el capítulo 4 se realiza la validación de las propuestas de las mejoras planteadas. En la primera etapa se contrataron 210 personas para eliminar el backlog y se validó una utilidad de 104 miles de soles. Para la segunda etapa, se implementó el proyecto cuadrillas propias y se utilizaron las metodologías Last Planner System y Vehicle Routing Problem.. Finalmente, se integró ambas metodologías con la incorporación de tecnología del tipo Workforce Management. Los resultados muestran una TIR del 20% y un VAN de 229 miles de soles. / The present research is about the implementation of low voltage electrical projects, which are performed by an utility company whose area of operations is the city of Lima. Chapter 1 describes the literature associated with the solution of the problem, where the theoretical framework of the above mentioned methodologies is developed. Chapter 2 describes the results obtained through the utilization of industrial engineering tools, with which the problem is identified as: "delays in the implementation of low voltage projects with reform". This problem generates an annual loss of 381 thousand soles and a working capital deficit of 11,500 thousand soles corresponding to year 2017. Chapter 3 proposes the solution of the exposed problem, for which two stages are defined. The first one allows the elimination of the accumulated backlog until September 2018. The second one refers to the development of the methodologies: Last Planner System, Vehicle Routing Problem and Workforce Management. Chapter 4 validates the proposed improvements. In the first stage, 210 people were hired to eliminate the backlog and as a result there was a profit of 104 thousand soles for the period within July and September. For the second stage, the project of own crews was implemented and there were used Last Planner System and the Vehicle Routing Problem as methodologies in order to optimize the route of the crews. Finally, both methodologies were integrated with the incorporation of the Workforce Management technology. The results show an IRR of 20% and a NPV of 229 thousand soles. / Trabajo de Suficiencia Profesional

In this paper we consider a rich vehicle routing problem where transportation requests are characterised by multiple pickup and delivery locations. The problem is a combined load acceptance and generalised vehicle routing problem incorporating a diversity of practical complexities. Among those are time window restrictions, a heterogeneous vehicle fleet with different travel times, travel costs and capacity, multi-dimensional capacity constraints, order/vehicle compatibility constraints, and different start and end locations for vehicles. We propose iterative improvement approaches based on Large Neighborhood Search and a relatedness measure for transportation requests with multiple pickup and delivery locations. Our algorithms are characterised by very fast response times and thus, can be used within dynamic routing systems where input data can change at any time.

In this thesis, the vehicle routing problem with stochastic, and time dependent, travel times is studied. The stochastic travel times are estimated from historical drive data. The variation of the drive times, as well as that of the variance, during the day was modeled.   The purpose of the thesis was to propose a method of handling the congestion related traffic impediments in an urban setting. Since the majority of times of delivery in the empirical test cases studied correlate with the time period of high traffic load, an efficient and robust handling of such traffic scenarios is of high importance.  It is shown that the stochastic models will shift the estimated arrivals to customers from the more volatile early and late extremes to more central regions of the time window. Previously delivered routes were evaluated both with the standard algorithm and the proposed stochastic algorithm. The difference between the actual drive times and the calculated drive times were analyzed by studying the correlation of the drive times between each customer in the route. It was shown that the routes of the proposed stochastic method increased this correlation. The drive times between nodes where also perturbed with a Gamma distributed noise. The results from the stochastic algorithm showed higher resilience to this disturbance than did the deterministic models. / I detta examensarbete har fordonsruttningsproblemet, VRP, med stokastiska och tidsberonds körtider behandlöats. De stokastiska körtiderna har estimerats från tidigare insamlad hasighetsdata. Modeller för körtidernas och variansernas förändring under dagen har tagits fram.   Syftet med examensarbetet var att föreslå en metod för hur påverkan på körtider av förutsägbar trafikträngsel i en urban trafikmiljö kan hanteras. Eftersom huvuddelen av alla leveranser sammanfaller med de tider på dygnet då trafikbelastning är som högst, ar är en effektiv och robust metod för att hantera sådana störningar av stor vikt. Det visas att den stokastiska modellen kommer att förflyttar ankomster från början och slutet av tidsfönstret till den mer okänsliga mittregionen. Tidigare, utförda leveranser studerades både med den ursprungliga deterministiska modellen och här framtagna stokastiska modellen. Skillnaden mellan de två analyserades genom att studera korrelationen mellan körtiderna som de beräknats av de två modellerna och de upmätta tiderna som de loggats av leveransfordonen. Det visas att korrelationen mellan körtiderna mellan de stokastiska körtiderna och de verkliga körtiderna är högre än korrelationen mellan de deterministiska körtiderna och de verkliga. Rutterna som föreslagits av den stokastiska modellen var också mer tlig mot störningar.

京都大学 / 0048 / 新制・課程博士 / 博士(工学) / 甲第19290号 / 工博第4087号 / 新制||工||1630(附属図書館) / 32292 / 京都大学大学院工学研究科都市社会工学専攻 / (主査)教授 谷口 栄一, 准教授 宇野 伸宏, 准教授 QURESHI,Ali Gul / 学位規則第4条第1項該当 / Doctor of Philosophy (Engineering) / Kyoto University / DFAM

Since Hurricane Katrina, extensive studies have been conducted aiming to optimize the transit vehicle routing in the event of an emergency evacuation. However, the vast majority of the studies focus on solving the deterministic vehicle routing problem that all the evacuation data are known in advance. These studies are generally not practical in dealing with real-world problems which involve considerable uncertainty in the evacuation data set. In this dissertation, a SmartEvac system is developed for dynamic vehicle routing optimization in emergency evacuation. The SmartEvac system is capable of processing dynamic evacuation data in real time, such as random pickup requests, travel time change, network interruptions. The objective is to minimize the total travel time for all transit vehicles. A column generation based online optimization model is integrated into the SmartEvac system. The optimization model is based on the following structure: a master problem model and a sub-problem model. The master problem model is used for routes selection from a restricted routes set while the sub-problem model is developed to progressively add new routes into the restricted routes set. The sub-problem is formulated as a shortest path problem with capacity constraint and is solved using a cycle elimination algorithm. When the evacuation data are updated, the SmartEvac system will reformulate the optimization model and generate a new routes set based on the existing routes set. The computational results on benchmark problems are compared to other studies in the literature. The SmartEvac system outperforms other approaches on most of the benchmark problems in terms of computation time and solution quality. CORSIM simulation is used as a test bed for the SmartEvac system. CORSIM Run-Time-Extension is developed for communications between the simulation and the SmartEvac system. A case study of the Hurricane Gustav emergency evacuation is conducted. Different scenarios corresponding to different situations that presented in the Hurricane Gustav emergency evacuation are proposed to evaluate the performance of the SmartEvac system in response to real-time data. The average processing time is 28.9 seconds and the maximum processing time is 171 seconds, which demonstrate the SmartEvac system’s capability of real-time vehicle routing optimization.

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 / 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

<p> In this thesis, we have considered the vehicle routing problem with pickup and delivery which is a generalization of the capacitated vehicle routing problem (CVRP). The vehicle routing problem with pickup and delivery (VRPPD) arises whenever pickup demand and delivery demand is to be satisfied by the same vehicle. The problem is encountered in many real life situations including reverse logistics. We consider three variants of VRPPD, namely, the vehicle routing problem with back-hauls (VRPB), the vehicle routing problem with back-hauls and mixed-load (VRPBM) and the vehicle routing problem with simultaneous pickup and delivery (VRPSPD). </p> <p> The inherent complexity of VRPPD makes it an NP -hard problem. It is not possible to solve an NP-hard problem in polynomial time unless P = NP. Therefore, heuristics and metaheuristics are used to produce a good quality solution within reasonable CPU time. We develop ant colony algorithms for VRPB, VRPBM and VRPSPD. We have improved the existing ant-colony algorithms by applying better local search schemes and by adding new features such as construction rule and the trail updating criteria. We also develop saving based heuristics for single and multi-depot versions of VRPSPD. Checking feasibility of a given route is an important issue in VRPSPD because of the fluctuating load on the vehicle. We have proposed the cumulative net-pickup approach for this purpose. One important feature of this approach is that it checks the feasibility of an altered route in constant time. </p> <p> The proposed heuristics and metaheuristics are evaluated by solving benchmark problem instances available in literature and then comparing the solutions with the solutions produced by the existing algorithms. Our computational experiment has shown that the proposed heuristics and metaheuristics give better or equally good results in comparison to the existing solution procedures. </p> / Thesis / Doctor of Philosophy (PhD)