Loading…

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!

cited_by	cdi_FETCH-LOGICAL-c327t-af50b248cd5f4bfa31ffd7c4f2e199ce837fb56fb8a87a5653c36230fe3e8d3f3
cites
container_end_page	310
container_issue	3
container_start_page	281
container_title	Transportation science
container_volume	16
creator	Assad, Arjang A
description	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.
doi_str_mv	10.1287/trsc.16.3.281
format	article
fullrecord	<record><control><sourceid>jstor_cross</sourceid><recordid>TN_cdi_jstor_primary_25768056</recordid><sourceformat>XML</sourceformat><sourcesystem>PC</sourcesystem><jstor_id>25768056</jstor_id><sourcerecordid>25768056</sourcerecordid><originalsourceid>FETCH-LOGICAL-c327t-af50b248cd5f4bfa31ffd7c4f2e199ce837fb56fb8a87a5653c36230fe3e8d3f3</originalsourceid><addsrcrecordid>eNqFj0tLxDAYRYMoWEeXLoUuXLgwNY_mMcth8AUDCo7rkKb5phk6rSQV8d_boT6Wru7innvhIHROSUGZVjdDTK6gsuAF0_QAZVQwiUVZqkOUEVJSTKUQx-gkpS0hVCgqMnS5yJetTSnvIV9HGzr84hpfv7eh2-TPsa9av0un6Ahsm_zZd87Q693tevmAV0_3j8vFCjvO1IAtCFKxUrtaQFmB5RSgVq4E5ul87rzmCiohodJWKyuk4I5Lxgl47nXNgc8Qnn5d7FOKHsxbDDsbPw0lZq9o9oqGSsPNqDjyFxO_TUMff2EmlNREyLG_nvrQQR936d-7qwlvwqb5CNGbn90QbZdc-EO_ABLuaz0</addsrcrecordid><sourcetype>Aggregation Database</sourcetype><iscdi>true</iscdi><recordtype>article</recordtype></control><display><type>article</type><title>A Class of Train-Scheduling Problems</title><source>Business Source Ultimate【Trial: -2024/12/31】【Remote access available】</source><source>JSTOR Archival Journals and Primary Sources Collection</source><creator>Assad, Arjang A</creator><creatorcontrib>Assad, Arjang A</creatorcontrib><description>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.</description><identifier>ISSN: 0041-1655</identifier><identifier>EISSN: 1526-5447</identifier><identifier>DOI: 10.1287/trsc.16.3.281</identifier><language>eng</language><publisher>INFORMS</publisher><subject>Greedy algorithms ; Heuristics ; Mathematical functions ; Motor vehicle traffic ; Objective functions ; Optimal policy ; Optimal solutions ; Railroad trains ; Scheduling ; Traffic</subject><ispartof>Transportation science, 1982-08, Vol.16 (3), p.281-310</ispartof><rights>Copyright © 1982 Operations Research Society of America</rights><lds50>peer_reviewed</lds50><woscitedreferencessubscribed>false</woscitedreferencessubscribed><citedby>FETCH-LOGICAL-c327t-af50b248cd5f4bfa31ffd7c4f2e199ce837fb56fb8a87a5653c36230fe3e8d3f3</citedby></display><links><openurl>$$Topenurl_article</openurl><openurlfulltext>$$Topenurlfull_article</openurlfulltext><thumbnail>$$Tsyndetics_thumb_exl</thumbnail><linktopdf>$$Uhttps://www.jstor.org/stable/pdf/25768056$$EPDF$$P50$$Gjstor$$H</linktopdf><linktohtml>$$Uhttps://www.jstor.org/stable/25768056$$EHTML$$P50$$Gjstor$$H</linktohtml><link.rule.ids>314,780,784,27924,27925,58238,58471</link.rule.ids></links><search><creatorcontrib>Assad, Arjang A</creatorcontrib><title>A Class of Train-Scheduling Problems</title><title>Transportation science</title><description>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.</description><subject>Greedy algorithms</subject><subject>Heuristics</subject><subject>Mathematical functions</subject><subject>Motor vehicle traffic</subject><subject>Objective functions</subject><subject>Optimal policy</subject><subject>Optimal solutions</subject><subject>Railroad trains</subject><subject>Scheduling</subject><subject>Traffic</subject><issn>0041-1655</issn><issn>1526-5447</issn><fulltext>true</fulltext><rsrctype>article</rsrctype><creationdate>1982</creationdate><recordtype>article</recordtype><recordid>eNqFj0tLxDAYRYMoWEeXLoUuXLgwNY_mMcth8AUDCo7rkKb5phk6rSQV8d_boT6Wru7innvhIHROSUGZVjdDTK6gsuAF0_QAZVQwiUVZqkOUEVJSTKUQx-gkpS0hVCgqMnS5yJetTSnvIV9HGzr84hpfv7eh2-TPsa9av0un6Ahsm_zZd87Q693tevmAV0_3j8vFCjvO1IAtCFKxUrtaQFmB5RSgVq4E5ul87rzmCiohodJWKyuk4I5Lxgl47nXNgc8Qnn5d7FOKHsxbDDsbPw0lZq9o9oqGSsPNqDjyFxO_TUMff2EmlNREyLG_nvrQQR936d-7qwlvwqb5CNGbn90QbZdc-EO_ABLuaz0</recordid><startdate>19820801</startdate><enddate>19820801</enddate><creator>Assad, Arjang A</creator><general>INFORMS</general><general>Transportation Science Section of the Operations Research Society of America</general><scope>AAYXX</scope><scope>CITATION</scope></search><sort><creationdate>19820801</creationdate><title>A Class of Train-Scheduling Problems</title><author>Assad, Arjang A</author></sort><facets><frbrtype>5</frbrtype><frbrgroupid>cdi_FETCH-LOGICAL-c327t-af50b248cd5f4bfa31ffd7c4f2e199ce837fb56fb8a87a5653c36230fe3e8d3f3</frbrgroupid><rsrctype>articles</rsrctype><prefilter>articles</prefilter><language>eng</language><creationdate>1982</creationdate><topic>Greedy algorithms</topic><topic>Heuristics</topic><topic>Mathematical functions</topic><topic>Motor vehicle traffic</topic><topic>Objective functions</topic><topic>Optimal policy</topic><topic>Optimal solutions</topic><topic>Railroad trains</topic><topic>Scheduling</topic><topic>Traffic</topic><toplevel>peer_reviewed</toplevel><toplevel>online_resources</toplevel><creatorcontrib>Assad, Arjang A</creatorcontrib><collection>CrossRef</collection><jtitle>Transportation science</jtitle></facets><delivery><delcategory>Remote Search Resource</delcategory><fulltext>fulltext</fulltext></delivery><addata><au>Assad, Arjang A</au><format>journal</format><genre>article</genre><ristype>JOUR</ristype><atitle>A Class of Train-Scheduling Problems</atitle><jtitle>Transportation science</jtitle><date>1982-08-01</date><risdate>1982</risdate><volume>16</volume><issue>3</issue><spage>281</spage><epage>310</epage><pages>281-310</pages><issn>0041-1655</issn><eissn>1526-5447</eissn><abstract>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.</abstract><pub>INFORMS</pub><doi>10.1287/trsc.16.3.281</doi><tpages>30</tpages></addata></record>
fulltext	fulltext
identifier	ISSN: 0041-1655
ispartof	Transportation science, 1982-08, Vol.16 (3), p.281-310
issn	0041-1655 1526-5447
language	eng
recordid	cdi_jstor_primary_25768056
source	Business Source Ultimate【Trial: -2024/12/31】【Remote access available】; JSTOR Archival Journals and Primary Sources Collection
subjects	Greedy algorithms Heuristics Mathematical functions Motor vehicle traffic Objective functions Optimal policy Optimal solutions Railroad trains Scheduling Traffic
title	A Class of Train-Scheduling Problems
url	http://sfxeu10.hosted.exlibrisgroup.com/loughborough?ctx_ver=Z39.88-2004&ctx_enc=info:ofi/enc:UTF-8&ctx_tim=2024-12-29T06%3A54%3A02IST&url_ver=Z39.88-2004&url_ctx_fmt=infofi/fmt:kev:mtx:ctx&rfr_id=info:sid/primo.exlibrisgroup.com:primo3-Article-jstor_cross&rft_val_fmt=info:ofi/fmt:kev:mtx:journal&rft.genre=article&rft.atitle=A%20Class%20of%20Train-Scheduling%20Problems&rft.jtitle=Transportation%20science&rft.au=Assad,%20Arjang%20A&rft.date=1982-08-01&rft.volume=16&rft.issue=3&rft.spage=281&rft.epage=310&rft.pages=281-310&rft.issn=0041-1655&rft.eissn=1526-5447&rft_id=info:doi/10.1287/trsc.16.3.281&rft_dat=%3Cjstor_cross%3E25768056%3C/jstor_cross%3E%3Cgrp_id%3Ecdi_FETCH-LOGICAL-c327t-af50b248cd5f4bfa31ffd7c4f2e199ce837fb56fb8a87a5653c36230fe3e8d3f3%3C/grp_id%3E%3Coa%3E%3C/oa%3E%3Curl%3E%3C/url%3E&rft_id=info:oai/&rft_id=info:pmid/&rft_jstor_id=25768056&rfr_iscdi=true