차량 라우팅/리소스 스케줄링 알고리즘 설계

Question

내 첫 번째 게시물 - 내가 잠시 동안 생각해 왔던 알고리즘을 설계하는 데 도움이되기를 바랍니다. - VRPTW 또는 리소스 스케줄링 또는 다른 것을 취할 방법이 확실하지 않습니다. 전적으로 !?)

실제 단어 예제에 넣으려면 적은 수의 위치 (일반적으로 5 개 미만)에서 많은 정원 쓰레기가 있습니다. 폐기물은 모두 주어진 시간 내에 다른 장소로 수송되어야합니다. 정원 폐기물을 옮기기 위해 우리는 트레일러로 견인해야합니다. 정원 쓰레기는 특정 시간 (시간대)에만 폐기물 저장소에 떨어 뜨릴 수 있습니다. 어떤 사이트에서는 트레일러에서 트레일러를 내려서 사람들이 채우거나 비울 수 있지만 다른 지역에서는 자동차 운전 기사가 직접해야하며 자동차는 거기에 머물러 있어야합니다. 모든 타이밍을 계산할 수 있습니다 (예 :로드/언로드 시간, 대중 교통 시간 등). 자동차는 예고편 없이도 사이트간에 이동할 수 있지만 예고편은 비었지만 예고편은 서로 이동할 수 없습니다.

은 "균형"

우리의 목표는 폐기물을 이탈에 대한 사용에 모든 시간 창을

회의 예고편 및 자동차의 수를 최소화

• 동안 전송되는 폐기물의 모든 트레일러 하중을 보장하는 것입니다 예고편 - 하루가 끝날 무렵에는 각 위치에 예고편이 여러 개 있습니다.

나는 이것을 자원 스케줄링 알고리즘을 사용하지만 트레일러의 "균형"을 처리하는 방법을 잘 모르겠습니다.

제가 고려한 다른 한 가지 방법은 자동차를 먼저 고려하는 것이 었습니다. 그런 다음 가장 빠른 작업을 선택하고 그 후에 가능한 모든 작업의 ​​그래프를 작성할 수 있습니다. 그런 다음 그래프를 통해 가장 긴 경로를 선택하면 최대 트레일러로드 수가 처리됩니다. 그런 다음 작업 목록에서 이러한 작업을 제거하고 모든 작업이 처리 될 때까지 반복 할 수있었습니다. 그런 다음 필요한 수의 예고편을 찾으려면이 예고편 목록을 실행해야합니다.

접근 방법에 대한 의견을 보내 주시면 감사하겠습니다.

Answer 1

나는 지리에 동의합니다 ...당신은 수용 할 수있는 솔루션과 합리적으로 가까운 거리에있는 휴리스틱 알고리즘을 원한다.

저는 이전에 회사에서 라우팅 라우팅 소프트웨어를 사용하고 있었고 접근 방법은 유전 알고리즘을 사용하여 매우 비슷하지만 매우 큰 규모의 문제를 해결했습니다. 접근 방식에 익숙하지 않은 경우 look here으로 가져 가세요. 해당 사이트에서 :

1. [시작] n 개의 염색체의 임의 인구 (문제에 적합한 솔루션)
2. [헬스] 인구의 각 염색체 x의 피트니스 F (X)를 평가를 생성

3. 새로운 인구가 완료 될 때까지 [뉴 인구는] 다음과 같은 단계를 반복하여 새로운 인구를 만들기

   [선택] (선택해야 더 나은 건강, 더 큰 기회) 자신의 체력에 따라 인구가 두 부모 염색체를 선택

   [교차] 크로스 오버 확률이 부모를 넘어 교차하여 새 자손 (어린이)을 형성합니다. 교차가 수행되지 않으면 자손은 부모의 정확한 사본입니다.

   [변이] 각 유전자좌 (염색체 내의 위치)에 돌연변이 확률로 새 새끼를 돌린다.

   새로운 인구의 새로운 자손을 놓고 [수락]

4. [교체] 최종 조건을 만족하는 경우
이
5. [테스트]를 중지 알고리즘의 추가 실행을위한 새로운 생성 된 인구를 사용하여 최적의 반환 현재 인구
6. [루프] 이동의 솔루션은 이에 대한 트릭은 "염색체"로 제약을 인코딩하고 "적합성"기능을 쓰고 2

단계. 피트니스 기능은 잠재적 솔루션의 결과를 입력 받아 제약 조건을 위반하는 경우 솔루션을 버리거나 버리는 것이 얼마나 좋은지 점수를 내야합니다.

지리가 언급했듯이이 솔루션의 장점은 실용적이지만 최상의 결과는 아니지만 매우 신속하게 답변을 제공하고 실행 시간을 길게할수록 더 좋은 솔루션을 얻을 수 있다는 것입니다.

Answer 2

우리는 NP 완성 알고리즘을 확실히 말하고 있습니다. 자동차 및 트레일러의 몇 가지 숫자를 넘어서는 모든 가능한 솔루션 중에서 최상의 솔루션을 얻은 다음이를 폐기하고 실행할 수있는 작업이 될 수 없습니다. 다시 말하면 가장 길은 길을 피하십시오. 그런 식으로 알고리즘을 설계한다면 언젠가 조금 더 많은 자동차와 트레일러를 추가 할 가능성이 높으며 솔루션 계산을 끝내지 못할 것입니다.

문제의 충분한 해결책을 비교적 빠르게 생성 할 수있는 알고리즘을 사용하고 싶을 것입니다. 솔루션의 품질에 대한 메트릭을 작성하고 이상적인 솔루션에 대한 메트릭 값을 추정하는 좋은 방법을 얻은 다음 솔루션을 이상적인 솔루션에서 얻고 자하는 몇 가지를 설정하고 경계 내에서 메트릭을 갖는 첫 번째 솔루션을 선택하십시오. 이것은이 알고리즘이 계산하는 데 너무 오래 걸리고 중단하는 경우 추가 이점이 있습니다. 예상 경계에 있지 않더라도 계산 된 메트릭이 가장 적은 솔루션을 계속 사용할 수 있습니다.

문제 자체를 해결하기 위해 어떤 접근 방식을 사용하는지 잘 모르겠습니다. acm portal에서 검색 한 후 몇 가지 기사를 읽으라고 제안합니다. 나는 UPS와 Fedex가 아마 비슷한 문제가 있다고 가정 할 것이고, 당신이 구글의 검색 키워드로 그들을 추가한다면, 당신은 좀 더 유용한 결과를 얻을 수있을 것이다.

Answer 3

나는 Robert와 동의하는 경향이 있습니다. 그가 말한 Genetic Algorithm 구현과 같은 진화 적 최적화 기술에 대한 훌륭한 후보자처럼 들립니다.

또한 PSO (Particle Swarm Optimization)의 특정 문제에 대해 매우 성공적으로 수행했습니다. 기본적으로 각 게놈을 다차원 공간의 입자로 생각할 수 있습니다. 입자의 좌표는 계산의 매개 변수입니다 (적합성 함수). 각 입자는 임의의 속도로 무작위로 시작됩니다. 시뮬레이션을 반복 할 때마다 각 입자의 위치를 ​​현재 이동 벡터로 업데이트 한 다음 다른 벡터의 구성 요소를 추가합니다. 예를 들어 지금까지 가장 좋은 입자 방향, 가장 좋은 입자 방향, 로컬 그룹 방향 최선 등 ...

처음에는 GA 나 PSO를 구현하는 것이 다소 어려울 수 있지만 실제로 문제 도메인에서 알고리즘 (GA/PSO)을 추상화하는 작은 프레임 워크를 작성하는 것은 쉽다는 것을 확신합니다. 당신은 최적화하려고합니다. 알고리즘에 대한 자세한 내용은 언제든지 위키피디아로 돌아갈 수 있습니다.

일단 프레임 워크가 생기면 일반적으로 2 매개 변수 문제 (문제의 단순화 또는 이미지의 X 및 Y 위치)로 시작하므로 알고리즘을 쉽게 시각화하고 조정하여 얻을 수 있습니다. 좋은 털복숭이는 행동. 그런 다음 더 많은 차원으로 확장합니다.

나는 자동차 및 트레일러와 같은 실제 문제 진술과 다소 복잡하고 복잡한 부분이있는 문제를 쉽게 최적화 할 수 있기 때문에이 접근 방식을 좋아합니다.

왜 진화 기술이 매력적인지는 고정 된 부분의 시간을 시뮬레이션에 할당 할 수 있고 중지하기로 결정했을 때 가장 좋은 대답을 얻을 수 있기 때문입니다.

내 경험상 하드 코딩 된 휴리스틱 솔루션을 작성하는 것처럼 GA 나 PSO에 매개 변수를 조정하는 데 많은 시간이 소요되는 경향이 있지만 장점은 다음과 같은 전략을 변경하는 것입니다. 문제를 해결하기 위해 완전히 다른 전략을 코딩하는 것과는 대조적으로 일반적으로 솔루션을 찾는 데는 매개 변수 변경 만 필요하거나 매우 잘 정의 된 알고리즘을 다른 구현으로 교체해야합니다.

두 알고리즘 중 하나의 일반 프레임 워크 디자인에 대한 지침이 필요하면 나에게 한마디 해주세요. 내가 지적해야 할 것은, 당신은 여러 가지 훌륭한 무료 제 3 자 프레임 워크를 제공한다는 것입니다. 때로는 알고리즘의 모든 측면을 이해하고 전략을 조정할 수있는 곳을 알기 때문에 코드를 직접 작성하고 싶습니다.

Answer 4

일반 접근법 :

문제가 작기 때문에 당신이 자동차와 트레일러를 최소화하기 위해 노력보다는 가능한 솔루션을 얻을 때까지, 당신이 자동차와 트레일러를 추가 접근 방식을 제안합니다.

해결 :

내가 제약 가스를 덜 성공하고, (예를 들어, 위치에 트레일러의 수) 정수 변수에 대한 제약 가스를 더 적은 성공을 거두었습니다

. 이동 거리를 최소화하기보다는 주어진 수의 자동차 및 트레일러에 대해 실현 가능한 솔루션을 생성하기를 원하기 때문에 제약 프로그래밍이 더 나은 접근 방법 일 수 있습니다.

관측 :

당신은 마지막으로 이동 빈 트레일러를 재배치 할 수있는 네트워크에 문제를 해결하고 있습니다.

행운을 빈다.

Answer 5

로컬 검색은 유전 알고리즘의 대안입니다. 국제 시간표 경쟁 2007에서 지역 검색 알고리즘 (예 : 금기 검색 및 시뮬레이트 된 어닐링)은 유전 알고리즘 항목 (LS는 약 1 위, 대다수는 약 80 위의 IIRC 중 1 위의 GA에 대해 5 위)을 분명히 이겼습니다.

OptaPlanner (Tabu Search, Simulated Annealing, Late Acceptance, 오픈 소스, 자바), JGap (유전 알고리즘, 오픈 소스, 자바), OpenTS (Tabu 검색, ...