A Hybrid Algorithm based on Monte-carlo Simulation for the Vehicle Routing Problem with Route Length Restrictions

Abstract

This chapter describes an approach based on Monte Carlo Simulation (MCS) to solve the Capacitated Vehicle Routing Problem (CVRP) with route length restrictions and customer service times. the additional restriction introduces further challenges to the classical CVRP. the basic idea behind our approach is to combine direct MCS with an efficient heuristic, namely the Clarke and Wright Savings (CWS) algorithm, and a decomposition technique. the CWS heuristic provides a constructive methodology which is improved in two ways: (i) a special random behavior is introduced in the methodology using a geometric distribution; and (ii) a divide-and-conquer technique is used to decompose the original problem in smaller sub-problems that are easier to deal with. the method is tested using a set of well-known benchmarks. the chapter discusses the advantages and disadvantages of the proposed procedure in relation to other approaches for solving the same problem. © 2012, IGI Global.

Department(s)

Engineering Management and Systems Engineering

International Standard Book Number (ISBN)

978-161350086-6

Document Type

Article - Journal

Document Version

Citation

File Type

text

Language(s)

English

Rights

© 2024 IGI Global; InformationResources Management Association, All rights reserved.

Publication Date

01 Dec 2011

Link to Full Text

Share

 
COinS