Mathematical Model of the Traveling Salesman Problem with Delivery and Draft Limit

Abstract

In this paper, we determine the order of the ports to be reached with the help of graph theory and establish Hamilton cycles. We obtain sub-solutions and solution sets with the help of these cycles. Moreover, we prove some relations about the draft limit and the demand of the port. Finally we present some examples.

Keywords

• Travelling salesman problem,Draft Limit,Maritime Transportation

References

1. Battara, M. Erdogan, G., Laporte G., jestvang, Vigo, D.(2010). The Traveling Salesman Problem with Pickups, Deliveries, and Handling Costs Transportation Science, 44(3): 383-99
2. Cordeau, J-F, Iori, M., Laporte, G., Salazar Gonzalez, JJ. (2010). A branch and cut agorithm for the pickup and delivery traveling salesman problem with LIFO loading. Networks ; 55(1):46-59
3. Fagerholt, K. and Christiansen, M. (2000). A traveling salesman problem with allocation, time window and precedence constraints - an application to ship scheduling. International Transactions in Operational Research, 7 , 231-244.
4. Erdogan, G., Cordeau, J-F., Laporte G. (2009). The pickup and delivery traveling salesman problem with firs in first out loading. Computers & Operations Research, ; 36(6):1800-8
5. Felipe, A., Ortuno, MT., Tirado, G. (2009). The double traveling salesman problem with multiple stacks: a variable neighborhood search approach. Computers & Operations Research, ; 36(11):2983-93
6. Henning, F. (2010). Optimization in maritime transportation: crude oil tanker routing and scheduling. PhD thesis. Norwegian University of Science and Technology;Iori, M., Martello, S. (2010). Routing problems with loading constraints. TOP; 18(1):4-27
7. Petersen, HL., Madsen OBG. (2009). The double traveling salesman problem with multiple stacks-formulation and heuristic solution approaches. European Journal of Operational Research ;198(1):139-47
8. Rakke, J. G., Christiansen, M., Fagerholt, K. and Laporte, G. (2012). The traveling salesman problem with draft limits. Computers & Operations Research, 39 (9) , 2161-2167.

9. Song J-H, Furman, KC. (2010). A maritime inventory routing problem: practical approach. Computers & Operations Research,