Effective solutions for the capacitated vehicle routing problem and for the split delivery vehicle routing problem with time windows. (c2013)

LAUR Repository

Show simple item record

dc.contributor.author Hilal, Nathalie
dc.date.accessioned 2013-09-03T10:15:46Z
dc.date.available 2013-09-03T10:15:46Z
dc.date.copyright 2013 en_US
dc.date.issued 2013-09-03
dc.date.submitted 2013-01-13
dc.identifier.uri http://hdl.handle.net/10725/1549
dc.description Includes bibliographical references (leaves 37-40). en_US
dc.description.abstract The Vehicle Routing Problem (VRP) is a generalization of the traveling salesman problem, and was initially proposed by Dantzig in order to find the optimum routing of a fleet of gasoline delivery trucks between a bulk terminal and a large number of service stations supplied by the terminal. Various variations of the VRP have been proposed such as the Capacitated VRP (CVRP) where all the customers correspond to deliveries and the demands are deterministic, known in advance, and may not be split. The vehicles are identical and based at a single central depot, and only the capacity restrictions for the vehicles are imposed. The objective is to minimize a weighted function of the number of routes and their travel time while serving all customers. Other Variations add pickup and delivery constraints (VRPPD), time windows constraints (VRPTW) and split delivery constraints (SDVRP). The Split Delivery Vehicle Routing Problem with Time Windows (SDVRPTW) combines the two main sub problems (SDVRP) and (CVRPTW). In this work, we present efficient solutions for solving the CVRP as well as the SDVRPTW, two combinatorial optimization problems. The algorithm starts with a greedy selective method that generates an initial solution then improves the solution using a combination of random and deterministic moves that are based on problem knowledge information. Experimental results are presented and favorable comparisons are reported. en_US
dc.language.iso en en_US
dc.subject Vehicle routing problem -- Mathematical models en_US
dc.subject Transportation problems (Programming) en_US
dc.subject Lebanese American University -- Dissertations en_US
dc.subject Dissertations, Academic en_US
dc.title Effective solutions for the capacitated vehicle routing problem and for the split delivery vehicle routing problem with time windows. (c2013) en_US
dc.type Thesis en_US
dc.term.submitted Fall en_US
dc.author.degree MS in Computer Science en_US
dc.author.school Arts and Sciences en_US
dc.author.idnumber 200103557 en_US
dc.author.commembers Dr. Danielle Azar
dc.author.commembers Dr. Chadi Nour
dc.author.woa OA en_US
dc.description.physdesc 1 bound copy: xii, 40 leaves; ill.; 31 cm. Available at RNL. en_US
dc.author.division Computer Science en_US
dc.author.advisor Dr. Haidar M. Harmanani
dc.keywords CVRP en_US
dc.keywords SDVRPTW en_US
dc.keywords SDVRP en_US
dc.keywords Simulated Annealing en_US
dc.keywords Meta-heuristic Approach en_US
dc.identifier.doi https://doi.org/10.26756/th.2013.14 en_US
dc.publisher.institution Lebanese American University en_US

Files in this item

This item appears in the following Collection(s)

Show simple item record

Search LAUR

Advanced Search


My Account