Gavigan, Kevin (1994) The design, development and application of a combined connectionist expert system and 'Pocket' Boltzmann machine approach to the Dynamic Customer Assignment and Vehicle Routing Problem. PhD thesis, University of Warwick.

Preview

PDF WRAP_Theses_Gavigan_1994.pdf - Submitted Version - Requires a PDF viewer. Download (13Mb) | Preview

Request Changes to record.

Abstract

This thesis describes the design, development and application of a combined connectionist expert system and ‘Pocket’ Boltzmann machine approach to a class of hard «¿»-complete combinatorial optimization problems.

The problem of efficiently incorporating additional routing demands to existing consignments is encountered by a number of organizations, including those providing Dial-A-Ride bus services, parcel collection and delivery services and in some warehousing and Automated Guided Vehicle systems. The conventional approach to examples from this class of problems is either to attempt to solve them manually or to develop dedicated algorithms.

This thesis describes a novel connectionist expert system approach which can obtain very good or (near-) optimal assignments of multiple customers to multiple vehicles in examples of capacitated, stochastic, un-split demand, multiple-vehicle assignment and routing problems.

Given an initial assignment of customers, distributed across a fleet of capacitated vehicles, a set of modified 'Pocket' Boltzmann machines are generated, which attempt to determine optimal initial routes for each of the vehicles in the fleet. At random times, variable numbers of new, un-split demand customers, with random locations and requiring assignment, are introduced into the system.

A connectionist expert system is generated - whose connection weights are partially determined using incremental cost data computed by a set of 'Pocket' Boltzmann machines - which attempts to optimally assign as many as possible of the new, un-split demand customers to the available capacitated vehicles for the smallest increase in the value of a total cost function. It is also demonstrated that in computing the incremental costs, the Pocket Boltzmann machines can generate very good or near optimal tours that also satisfy a variable number of addtional hard (mandatory) constraints.

Item Type:	Thesis (PhD)
Subjects:	Q Science > QA Mathematics Q Science > QA Mathematics > QA76 Electronic computers. Computer science. Computer software T Technology > TA Engineering (General). Civil engineering (General)
Library of Congress Subject Headings (LCSH):	Transport theory|xMathematical models., Lattice Boltzmann methods, Machine learning, Algorithms, Vehicle routing problem, Combinatorial optimization
Official Date:	June 1994
Dates:	Date Event June 1994 UNSPECIFIED
Institution:	University of Warwick
Theses Department:	School of Engineering
Thesis Type:	PhD
Publication Status:	Unpublished
Supervisor(s)/Advisor:	Hessey, Mike
Format of File:	pdf
Extent:	xiv, 303 leaves : illustrations
Language:	eng

Request changes or add full text files to a record

Repository staff actions (login required)

View Item

Downloads