스케줄링 문제를위한 기존 알고리즘?

Question

의 내가 제대로 다음과 같은 제약 주에서 운전하는 세 개의 버스 드라이버를 예약 할 기능을 구축하고자한다고 가정 해 봅시다 :

• 주 당 5 배를 운전해서는 안 각 드라이버는
• 이 있어야합니다 이 드라이버들은 알고리즘의 어떤 종류의이 같은 문제를 해결하기 위해 사용되는

(다른 드라이버 '휴식 일에 충돌하지 않습니다) 일일 매주 휴식 것입니다 일상

운전?

나는 여러 사이트를 통해 보면서 나는이 발견 : 나는 과거에 선형 계획법의 종류를 배운 적이없는 것처럼

1) Backtracking algorithm (brute force) 
2) Genetic algorithm 
3) Constraint programming 

는 솔직히이 나를 위해 모든 "문화 충격"입니다. 내가 알고 싶은 두 가지가 있습니다 :

1) 위의 사례 시나리오에 가장 적합한 알고리즘은 어느 것입니까?

2)이 문제를 해결하는 가장 간단한 알고리즘은 무엇입니까?

3) 위의 문제를 해결하기 위해 내가 조사 할 수있는 다른 알고리즘을 제안하십시오.

Answer 1

우선이 문제는 개별적인 최적화 문제이므로 선형 프로그래밍은 좋은 생각이 아닐 수 있습니다 (연속 최적화를위한 것이므로). 선형 프로그래밍 (정수 또는 혼합 정수 프로그램이 될 것입니다)을 사용하여이 문제를 해결할 수는 있지만 지수가 들립니다 (입력 크기가 작 으면 괜찮습니다). 이제 다시 비교에

:

1. 브 루트 포스 : 최악.

2. 유전체 : 최적 성을 보장 할 수 없습니다. 알고리즘이 문제를 해결하지 못할 수도 있습니다.

3. 제약 프로그래밍 : 확실히이 경우 (그리고 많은 개별 최적화 문제에서) 가장 좋습니다. IBM ILOG CPLEX 솔버에서이를 매우 효율적으로 구현합니다 (그러나 무료는 아니며 학계 또는 테스트 용으로 무료 임).

Answer 2

1) 나는 무차별 폭력이 나쁘다는 것에 동의합니다.

2) 문제가 정수 문제입니다. 그들은 선형 프로그래밍으로 해결할 수 있습니다.

3) 두 가지 접근 방식을 추론 할 수 있습니다. 즉, 경험적 방법과 정확한 접근 방식입니다. 인공 지능은 합리적인 계산 시간에 좋은 솔루션을 제공합니다. 계산 시간에 엄격한 요구 사항이 있거나 최적의 솔루션을 계산하기가 너무 어려울 때 사용됩니다. 유전 알고리즘은 경험적 방법입니다.

문제가 비교적 간단하기 때문에 정확한 접근 방식을 취할 것입니다.

4)이 문제를 해결하는 표준 방법은 분기 프로그램 & 바운드 검색 트리에 선형 프로그램을 포함시키는 것입니다.그것에 관한 많은 문헌이 있습니다.

1. 가 분기하는 부분 변수를 찾아 단순 알고리즘
2. 으로 선형 프로그램 해결 :이 절차는 다음과 같이 요약 될 수있다. 나는. X = 1

을 가리 키도록

이동 (일부 전략으로 선택) 1.5

두 개의 새로운 노드를 생성하고 X < = 1, X> = 2는 각각

이 하나 개의 노드로 이동 제약 조건을 추가 또한 트리의 모든 노드에서 지점 1 이후에 알고리즘은 노드를 프 i 할 수 있는지 여부를 확인합니다. 문제가 불가능한되었다

a),

b) 더 나은 해결책이 이미 존재

c) 정수 해법이 발견되기 때문에,이 노드로부터 "깊은"탐색을 중지하는 것을 의미한다. 이 솔루션의이 객관적인 가치는 점 b를 결정하는 데 사용됩니다.

모든 노드를 프 i (prune)하면 절차가 완료됩니다.

운 좋게도 Nicolas가 말했듯이이 작업을 수행하는 무료 구현이 있습니다. 모델을 작성하기 만하면됩니다. 일부 도구에서 목표와 제약 조건을 코드화하고 해결하도록합니다.