공장설계및실습 과제4.TSP

목차

Ⅰ. TSP 문제정의
Ⅱ. TSP 문제풀이
Ⅲ. Vehicle Routing Problems 문제정의
Ⅳ. Vehicle Routing Problems 문제풀이
Ⅴ. Reference

본문내용

Q2. Vehicle Routing Problems
Using the distance of below table, apply the Clarke & Wright heuristic to following vehicle scheduling problem. City 10 is the depot at which a delivery truck is stationed.
The truck has a carrying capacity of 10,000 lbs., and 4,000 cu.ft. Deliveries are scheduled at each of the other nine cities.
The volume and weight of these deliveries are follows. How many truck trips are useful in the solution?

1. TSP(Traveling Salesman Problem) 문제정의

- Traveling Salesman problem(TSP) 는 외판원 순회라고 불리는 문제로 computer science 분야에서 가장 중요하게 취급되는 문제 중 하나이다.
여러 가지 변종 문제가 있으나, 여 기서는 가장 일반적인 형태의 문제이다.
그래프에서 출발점으로부터 모든 노드를 1번씩 방문하고 다시 출발점으로 돌아올 수 있는 경로를 해밀턴 싸이클이라 한다. 그리고 해 밀턴 싸이클 중 가장 비용이 적은 것을 구하는 것이 외판원 문제 (TSP)이다. 문제에선 노드 간 이동이 불가할 때 가중치는 무한대가 아닌 0으로 하기로 했다.

2. TSP(Traveling Salesman Problem) 문제풀이

- 1번부터 10번까지 번호가 매겨져 있는 도시들이 있고, 도시들 사이에는 길이 있다.
이제 한 외판원이 어느 한 도시에서 출발해 10개의 도시를 모두 거쳐 다시 원래의 도시로 돌아오는 순회 여행 경로를 계획하려고 한다. 단, 한번 갔던 도시로는 다시 갈 수 없다. 또, 맨 마지막에 여행을 출발했던 도시로 돌아와야 한다.

참고자료

· TSP – Infrastructure for the Traveling Salesperson Problem, Michael Hahsler, Kurt Hornik
· J.E.Bell and P.R. McMullen. Ant Colony Optimisation Techniques for the Vehicle Routing Problem. Advanced, Engineering Informatics, 2004
· Management and Pperations, 2nd ed. C.Haksever, B. Render, R.Russell, and R. Murdick, 2000
· VEHICLE ROUTING, Dr.Campbell
· http://www3.cs.stonybrook.edu/~algorith/files/traveling-salesman.shtml