Random Sequences in Vehicle Routing Problem

Download

thesis_mehmetemingulsen_4.pdf

Date

2022-9-1

Author

Gülşen, Mehmet Emin

Metadata

Show full item record

This work is licensed under a Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International License.

Item Usage Stats

466
views

147
downloads

Vehicle Routing Problem (VRP) is a classical combinatorial optimization and integer programming problem. The goal of VRP is to find the optimal set of routes to given set of destination points with a fleet of vehicles. In this thesis, we have focused on the a variant of VRP which is Capacitated Vehicle Routing Problem (CVRP) and present two different combination of heuristic algorithms with random projection clustering technique and also provide comparison of random number generators on Monte Carlo Simulation to solve CVRP instances with combination of random projection cluster- ing algorithm. In the first part, we show that the random projection clustering ap- proach improves the cost compared to the core heuristic solution. In the second part, we study the choice of the random number generators on simulation based techniques on CVRP. A Monte Carlo simulation based Clarke and Wright’s Savings (CWS) al- gorithm implemented and experiments conducted with five different random number generators. Results have shown the choice of random number generators affects the performance of the simulation.

Subject Keywords

Monte Carlo Simulation, Random Number Generators, Capacitated Vehicle Routing Problem, Random Projection Clustering

URI

https://hdl.handle.net/11511/99506

Collections

Graduate School of Applied Mathematics, Thesis

Suggestions

OpenMETU
Core

Improvement of the Gravitational Search Algorithm by means of Low-Discrepancy Sobol Quasi Random-Number Sequence Based Initialization Altinoz, O. Tolga; YILMAZ, ASIM EGEMEN; Weber, Gerhard Wilhelm (2014-01-01) Nature-inspired optimization algorithms can obtain the optima by updating the position of each member in the population. At the beginning of the algorithm, the particles of the population are spread into the search space. The initial distribution of particles corresponds to the beginning points of the search process. Hence, the aim is to alter the position for each particle beginning with this initial position until the optimum solution will be found with respect to the pre-determined conditions like maximu...
Nonlinear Seismic Dam and Foundation Analysis Using Explicit Newmark Integration Method with Static Condensation Albostan, Utku; Bahcecioglu, Tunc; Arıcı, Yalın; Kurç, Özgür (Elsevier BV; 2017-09-13) Engineers use the explicit Newmark integration method to analyze nonlinear dynamic problems. Instead of using computationally expensive global matrix assembly and factorization, the explicit integration method performs computations at element level which is computationally efficient, easily parallelizable, and does not require equilibrium iterations in case of nonlinear analysis. On the other hand, the explicit schema might require much smaller time steps compared to implicit integration alternative especia...
Convergence Error Estimation and Convergence Acceleration in Iteratively Solved Problems Eyi, Sinan (null; 2012-07-09) New methods are developed for convergence error estimation and convergence acceleration in iteratively solved problems. The convergence error estimation method is based on the eigenvalue analysis of linear systems, but it can also be used for nonlinear systems. The convergence of iterative method is accelerated by subtracting convergence error from the iteratively calculated solutions. The performances of these methods are demonstrated for the Laplace, Euler and NavierStokes equations.
Approximate Analytical Solutions for the Weight Optimization Problems of CI and ICI Orguner, Umut (2017-10-12) Approximate analytical formulae are proposed for the solutions of the weight optimization problems involved in Covariance Intersection (CI) and Inverse Covariance Intersection (ICI). The methodology used for obtaining the analytic approximations boils down to using just two Newton iterations with the initial weight value 1/2. The simulation results show that quite acceptable root-mean-square (RMS) error levels are achievable with the proposed approximate analytical weights with less computations compared to...
Continuity problem for singular BSDE with random terminal time Samuel, Sharoy Augustine; Popier, Alexandre; Sezer, Ali Devin (2022-1-01) All Rights Reserved.We study a class of non-linear Backward stochastic differential equations (BSDE) with a superlinear driver process f adapted to a filtration F and over a random time interval [[0, S]] where S is a stopping time of F. The terminal condition ξ is allowed to take the value +∞, i.e., singular. We call a stopping time S solvable with respect to a given BSDE and filtration if the BSDE has a minimal supersolution with terminal value 1 at terminal time S. Our goal is to show existence of solutio...

Citation Formats

M. E. Gülşen, “Random Sequences in Vehicle Routing Problem,” M.S. - Master of Science, Middle East Technical University, 2022.