Routing and Scheduling on a Shoreline with Release Times
In this paper we examine computational complexity issues and develop algorithms for a class of "shoreline" single-vehicle routing and scheduling problems with release time constraints. Problems in this class are interesting for both practical and theoretical reasons. From a practical persp...
| Main Authors: | , , , |
|---|---|
| Format: | Working Paper |
| Language: | en_US |
| Published: |
Massachusetts Institute of Technology, Operations Research Center
2004
|
| Online Access: | http://hdl.handle.net/1721.1/5219 |
| _version_ | 1826212801210744832 |
|---|---|
| author | Psaraftis, Harilaos N. Solomon, Marius M. Magnanti, Thomas L. Kim, Tai-Up |
| author_facet | Psaraftis, Harilaos N. Solomon, Marius M. Magnanti, Thomas L. Kim, Tai-Up |
| author_sort | Psaraftis, Harilaos N. |
| collection | MIT |
| description | In this paper we examine computational complexity issues and develop algorithms for a class of "shoreline" single-vehicle routing and scheduling problems with release time constraints. Problems in this class are interesting for both practical and theoretical reasons. From a practical perspective, these problems arise in several transportation environments. For instance, in the routing and scheduling of cargo ships, the routing structure is "easy" because the ports to be visited are usually located along a shoreline. However, because release times of cargoes at ports generally complicate the routing structure, the resulting routing and scheduling problem is nontrivial. From a theoretical perspective, this class of problems lies on the borderline between problems in P and those that are NP-complete. For the straight-line case (a restriction of the shoreline case), our analysis shows that the problem of minimizing maximum completion time can be solved exactly in quadratic time by dynamic programming. For the shoreline case we develop and analyze heuristic algorithms. We derive data-dependent worst-case performance ratios for these heuristics. We also discuss how these algorithms perform on practical data. Finally, we examine the computational complexity of other problem variants involving alternative objective functions and different types of time window constraints. |
| first_indexed | 2024-09-23T15:38:26Z |
| format | Working Paper |
| id | mit-1721.1/5219 |
| institution | Massachusetts Institute of Technology |
| language | en_US |
| last_indexed | 2024-09-23T15:38:26Z |
| publishDate | 2004 |
| publisher | Massachusetts Institute of Technology, Operations Research Center |
| record_format | dspace |
| spelling | mit-1721.1/52192019-04-10T15:18:14Z Routing and Scheduling on a Shoreline with Release Times Psaraftis, Harilaos N. Solomon, Marius M. Magnanti, Thomas L. Kim, Tai-Up In this paper we examine computational complexity issues and develop algorithms for a class of "shoreline" single-vehicle routing and scheduling problems with release time constraints. Problems in this class are interesting for both practical and theoretical reasons. From a practical perspective, these problems arise in several transportation environments. For instance, in the routing and scheduling of cargo ships, the routing structure is "easy" because the ports to be visited are usually located along a shoreline. However, because release times of cargoes at ports generally complicate the routing structure, the resulting routing and scheduling problem is nontrivial. From a theoretical perspective, this class of problems lies on the borderline between problems in P and those that are NP-complete. For the straight-line case (a restriction of the shoreline case), our analysis shows that the problem of minimizing maximum completion time can be solved exactly in quadratic time by dynamic programming. For the shoreline case we develop and analyze heuristic algorithms. We derive data-dependent worst-case performance ratios for these heuristics. We also discuss how these algorithms perform on practical data. Finally, we examine the computational complexity of other problem variants involving alternative objective functions and different types of time window constraints. 2004-05-28T19:28:40Z 2004-05-28T19:28:40Z 1986-09 Working Paper http://hdl.handle.net/1721.1/5219 en_US Operations Research Center Working Paper;OR 152-86 1744 bytes 2539926 bytes application/pdf application/pdf Massachusetts Institute of Technology, Operations Research Center |
| spellingShingle | Psaraftis, Harilaos N. Solomon, Marius M. Magnanti, Thomas L. Kim, Tai-Up Routing and Scheduling on a Shoreline with Release Times |
| title | Routing and Scheduling on a Shoreline with Release Times |
| title_full | Routing and Scheduling on a Shoreline with Release Times |
| title_fullStr | Routing and Scheduling on a Shoreline with Release Times |
| title_full_unstemmed | Routing and Scheduling on a Shoreline with Release Times |
| title_short | Routing and Scheduling on a Shoreline with Release Times |
| title_sort | routing and scheduling on a shoreline with release times |
| url | http://hdl.handle.net/1721.1/5219 |
| work_keys_str_mv | AT psaraftisharilaosn routingandschedulingonashorelinewithreleasetimes AT solomonmariusm routingandschedulingonashorelinewithreleasetimes AT magnantithomasl routingandschedulingonashorelinewithreleasetimes AT kimtaiup routingandschedulingonashorelinewithreleasetimes |