TITLE

The Arc Routing and Scheduling Problem with Transshipment

AUTHOR(S)
Rosa, Barbara De; Improta, Gennaro; Ghiani, Gianpaolo; Musmanno, Roberto
PUB. DATE
August 2002
SOURCE
Transportation Science;Aug2002, Vol. 36 Issue 3, p301
SOURCE TYPE
Academic Journal
DOC. TYPE
Article
ABSTRACT
This article introduces the Arc Routing and Scheduling Problem with Transshipment (ARPT), a particular Arc Routing Problem whose applications arise in garbage collection. In the ARPT, the demand is collected by specially equipped vehicles, taken to a transfer station, shredded or compacted and, finally, transported to a dump site by means of high-capacity trucks. A lower bound, based on a relaxation of an integer linear formulation of the problem, is developed for the ARPT. A tailored Tabu Search heuristic is also devised. Computational results on a set of benchmark instances are reported.
ACCESSION #
7206238

 

Related Articles

  • A DUAL-ASCENT PROCEDURE FOR LARGE-SCALE UNCAPACITATED NETWORK DESIGN. Balakrishnan, A.; Magnanti, T. L.; Wong, R. T. // Operations Research;Sep/Oct89, Vol. 37 Issue 5, p716 

    The fixed-charge network design problem arises in a variety of problem contexts including transportation, communication, and production scheduling. We develop a family of dual-ascent algorithms for this problem. This approach generalizes known ascent procedures for solving shortest path, plant...

  • The Multiregion Dynamic Capacity Expansion Problem, Part II. Fong, C. O.; Srinivasan, V. // Operations Research;Jul/Aug81, Vol. 29 Issue 4, p800 

    Consider the problem of determining a schedule of capacity expansions for m producing regions and a schedule of shipments from the regions to the n markets so as to meet the market demands over a T-period planning horizon at minimum discounted capacity expansion and shipment costs. The capacity...

  • Error Bound of a Heuristic for the Common Due Date Scheduling Problem. Liman, Surya Danusaputro; Chung-Yee Lee // ORSA Journal on Computing;Fall93, Vol. 5 Issue 4, p420 

    In this paper, a simple heuristic for the n-job, one-machine nonpreemptive scheduling problem of minimizing the sum of absolute deviations of job completion times about a common due date is proposed. The heuristic, which has a complexity of O(n log n), is shown to hera a tight relative worst...

  • Recent results on resource-constrained project scheduling with time windows: Models, solution methods, and applications. Neumann, Klaus; Schwindt, Christoph; Zimmermann, Jürgen // Central European Journal of Operations Research;Jul2002, Vol. 10 Issue 2, p113 

    Presents survey results on deterministic project scheduling with time windows. Presentation of heuristic solutions method in the analysis; Applications of resource-constrained project scheduling to make-to-order production in manufacturing and investment projects; Modifications on the basic...

  • The Multiregion Dynamic Capacity Expansion Problem, Part I. Fong, C. O.; Srinivasan, V. // Operations Research;Jul/Aug81, Vol. 29 Issue 4, p787 

    Consider the problem of determining a schedule of capacity expansions for m producing regions and a schedule of shipments from the regions to n markets so as to meet the market demands over a T-period planning horizon at minimum discounted capacity expansion and shipment costs. Both of these...

  • Effective search space control for large and/or complex driver scheduling problems. Kwan, Raymond S. K.; Kwan, Ann // Annals of Operations Research;Nov2007, Vol. 155 Issue 1, p417 

    For real life bus and train driver scheduling instances, the number of columns in terms of the set covering/partitioning ILP model could run into billions making the problem very difficult. Column generation approaches have the drawback that the sub-problems for generating the columns would be...

  • Due window scheduling with sequence-dependent setup on parallel machines using three hybrid metaheuristic algorithms. Behnamian, J.; Zandieh, M.; Ghomi, S. M. T. Fatemi // International Journal of Advanced Manufacturing Technology;Feb2010, Vol. 44 Issue 7/8, p795 

    Due-date determination problems have gained significant attention in recent years due to the industrial focus in the just-in-time philosophy. This paper considers a machine scheduling problem where jobs should be completed at times as close as possible to their respective due dates, and hence,...

  • A Class of Train-Scheduling Problems. Assad, Arjang A. // Transportation Science;Aug82, Vol. 16 Issue 3, p281 

    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...

  • Optimizing Single Vehicle Many-to-Many Operations with Desired Delivery Times: II. Routing. Sexton, Thomas R.; Bodin, Lawrence D. // Transportation Science;Nov85, Vol. 19 Issue 4, p411 

    The article focuses on the routing subproblem. The authors present a heuristic algorithm for finding an initial route and a second heuristic algorithm for improving the route sequence. The heuristic algorithm places the pickup of the customer with the smallest latest feasible pickup time, as the...

Share

Read the Article

Courtesy of THE LIBRARY OF VIRGINIA

Sorry, but this item is not currently available from your library.

Try another library?
Sign out of this library

Other Topics