Browse Prior Art Database

Bus Crew Schedule Generation

IP.com Disclosure Number: IPCOM000080402D
Original Publication Date: 1973-Dec-01
Included in the Prior Art Database: 2005-Feb-27
Document File: 3 page(s) / 18K

Publishing Venue

IBM

Related People

Capra, R: AUTHOR [+2]

Abstract

A program is described providing a heuristic solution for the problem of generating bus crew schedules for extra urban operation, according only to a given timetable and satisfying union/management agreement.

This text was extracted from a PDF file.
At least one non-text object (such as an image or picture) has been suppressed.
This is the abbreviated version, containing approximately 66% of the total text.

Page 1 of 3

Bus Crew Schedule Generation

A program is described providing a heuristic solution for the problem of generating bus crew schedules for extra urban operation, according only to a given timetable and satisfying union/management agreement.

The problem, therefore, is to start from the timetable and to generate duties, defined by (1.1)*, (1.2) and (1.3), in such a way that the conditions (3) comply with the parameters N(T), E(T), S(T), and G(T) as defined by (2.1), (2.2), (2.3) and (2.4).

Let G=(X,U) be the oriented graph where X is the set of runs of the timetable assigned and:

(Image Omitted)

Clearly each run must belong to one and only one of the paths; the problem, therefore, becomes that of covering X by means of disjoint paths mu. (*) For a definition of this reference (1.1) and subsequent references (1.2), (1.3), (2.1),
(2.2), (2.3), (2.4) and (3) see BUS CREW DUTY COST MINIMIZATION by R. Capra, S. Lena and U. Santarelli, IBM Technical Disclosure Bulletin, December, 1973, Vol. 16 No. 7, pages 2181 to 2185. Let gamma(x) be the set of successors to x:

(Image Omitted)

Research for the best solution leads to the exploration of a decision tree, in which the number of the nodes has the order of:

(Image Omitted)

Even starting from problems of modest dimensions, this number assumes such high values that the explicit enumeration is practically inapplicable.

A heuristic criterion is therefore assumed, which, having arrived at exploration of the G graph at the x node, wo...