작업을 선형 프로그래밍으로 변환

Question

저는 자동화 된웨어 하우스 (지게차 포함)를 구성 할 때 이와 같은 문제가 있습니다. 하루의 시작에는 창고의 팔레트 랙에 팔레트가 있으며 하루 동안 팔레트를 창고로 가져 오거나 내보낼 수있는 몇 가지 구체적인 트럭이 있습니다. 또한 하루 동안 지게차의 주행 거리를 최소화하고 출고를 처리중인화물 트럭의 대기 시간을 최소화하고 싶습니다. (트럭 운전사가 팔레트를 가득 채울 때까지 기다리는 중입니다.)

나는 아주 직관적 인 몇 가지 알고리즘을 제안했지만 가장 직관적 인 방법 - 가져온 팔레트를 창고의 가장 가까운 프리 랙에 넣으면 좋은 결과를 내지 못합니다. 이 문제를 선형 프로그래밍으로 변환하려고 시도했지만 성공하지 못했습니다. 개별 트럭에 대한 최소화 된 지게차 경로를 찾는 방법을 알고 있지만, 트럭을 내보낼 때마다/창고 상태가되는 팔레트를 가져올 때마다 함께 배치하는 방법을 모릅니다. 변경됨 (창고의 다른 팔레트 레이아웃). 나는 체계적으로 모든 가능성을 검사하여 최상의 결과를 찾는 brute-force 방법을 시도했지만, 이것은 합리적인 시간에 결과를 산출하지는 못합니다 ...

아무도 아이디어가 있으십니까?

Answer 1

몇 가지 아이디어가 있습니다.

이 문제를 LP 표준 형식으로 변환 할 수없는 것 같습니다. 호출하는 LP의 표준 양식을

그런 다음 지게차의 이동 거리, 최적화하려는 경우입니다 - C 각 지게차를 운영 비용의 벡터이며, 이 될 것입니다 #lorries x #forklifts 계산할 수있는 최적의 거리가 포함 된 솔루션 x은 각 지게차에 작업량의 일부를 할당합니다.

시스템 제한 조건에 따라 벡터 b을 알아야합니다. 즉, b [i]는 평균 속도를 기준으로 지게차가 주행 할 수있는 최대 거리가 될 수 있습니다.

실제 정수 솔루션을 적절한 정수 솔루션으로 변환 할 수 있다면 정수형 선형 프로그래밍을 사용해야 할 것입니다. 이는 훨씬 더 어려운 최적화 문제입니다.

마지막으로웨어 하우스에서 팔레트를 움직이면 시스템 비용이 변경되고 LP는 적용되지 않으므로 일종의 상태 공간 검색을 사용해야합니다 (가장 먼저, A * 또는 일부 다른 변형) 팔레트, 지게차 및 화물차의 위치에 의해 상태가 정의됩니다.