픽업배달문제 (Pickup and Delivery Problem)
쉽게 풀면
택배 기사가 여러 곳에서 물건을 싣고 또 다른 여러 곳에 물건을 내려줘야 한다고 생각해보면 됩니다. 이때 한 물건은 반드시 실은 뒤에 내려줘야 하고, 차량이 한 번에 실을 수 있는 양에도 한계가 있습니다. 픽업배달문제는 이런 조건을 지키면서 가장 짧은 거리 또는 가장 적은 비용으로 모든 물건을 나를 경로를 찾는 문제입니다. 카카오T나 우버 같은 차량 호출 서비스의 배차 로직도 이 문제의 응용에 가깝습니다.
왜 중요한가
전자상거래와 라스트마일 배송, 콜택시·카풀 배차 산업이 커지면서 픽업과 배달을 동시에 고려하는 경로 설계의 중요성이 커졌습니다. 산업공학에서는 이 문제를 통해 물류 비용 절감과 서비스 응답 시간 단축을 동시에 달성하는 방법을 연구합니다.
논문에서는 이렇게 쓰입니다
화물이 특정 시간대 안에 픽업·배달되어야 하는 현실적 제약을 반영한 연구임을 보여줍니다.
승객 이동 서비스에서도 픽업배달문제 프레임워크가 활용됨을 나타냅니다.
조금 더 깊게 보면
픽업배달문제는 차량경로문제(VRP)의 확장 형태로 분류되며, 하나의 차량이 여러 픽업-배달 쌍을 처리하는 단일차량형과 여러 차량이 함께 처리하는 다차량형으로 나뉩니다. 실시간으로 요청이 들어오는 환경을 다루는 동적 픽업배달문제(Dynamic PDP)도 활발히 연구되고 있으며, 해법으로는 정확해를 구하는 정수계획법과 대규모 문제에 적합한 유전알고리즘·타부서치 등의 메타휴리스틱이 함께 사용됩니다.
주의할 점
일반적인 차량경로문제와 달리 픽업과 배달의 선후 관계, 동일 차량 내 처리라는 추가 제약이 있어 문제 복잡도가 더 높습니다. 실제 서비스에서는 교통 상황 변화 등 불확실성까지 고려해야 하므로 이론적 최적해와 실무 적용 사이에는 차이가 있을 수 있습니다.