A Class of Train-Scheduling Problems

We relate the question of determining stop-schedules for trains that deliver traffic on a line of stations to the maximization of submodular set functions. We prove that a greedy algorithm is optimal under certain assumptions and report computational experience on the performance of the greedy heuri...

Full description

Saved in:
Bibliographic Details
Published in:Transportation science 1982-08, Vol.16 (3), p.281-310
Main Author: Assad, Arjang A
Format: Article
Language:English
Subjects:
Greedy algorithms
Heuristics
Mathematical functions
Motor vehicle traffic
Objective functions
Optimal policy
Optimal solutions
Railroad trains
Scheduling
Traffic
Citations: Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:We relate the question of determining stop-schedules for trains that deliver traffic on a line of stations to the maximization of submodular set functions. We prove that a greedy algorithm is optimal under certain assumptions and report computational experience on the performance of the greedy heuristic as compared to the exact algorithm when the optimality of the greedy heuristic cannot be guaranteed.
ISSN:0041-1655
1526-5447
DOI:10.1287/trsc.16.3.281