●  사용방법 · 경로 · 물류

픽업 · 배송 (PDPTW)

요청마다 같은 차량이 먼저 픽업하고 나중에 배송해야 합니다. 그 사이 어느 시점에도 적재량을 넘으면 안 됩니다.

무엇을 정하나요

요청마다 맡을 차량 한 대와, 그 경로에서 픽업과 배송의 위치를 정합니다. 넣을 수 없는 요청은 픽업과 배송을 통째로 미배정으로 둡니다.

최소 실행 예제

from optimaru.pickup_delivery.models import (
    DeliveryModel, PdpInput, PdpRequest, StopModel, VehicleModel, solve_request,
)

request = PdpRequest(
    timelimit=2,
    random_seed=42,
    model_input=PdpInput(
        vehicles=[
            VehicleModel(id="V1", capacity=10, home=(37.5665, 126.9780), departure_time=8 * 3600),
        ],
        deliveries=[
            DeliveryModel(
                id="R1", demand=6,
                pickup=StopModel(id="R1-P", location=(37.5700, 126.9820), service_duration=300),
                dropoff=StopModel(id="R1-D", location=(37.5512, 126.9882), service_duration=300),
            ),
            DeliveryModel(
                id="R2", demand=6,
                pickup=StopModel(id="R2-P", location=(37.5133, 127.1001), service_duration=300),
                dropoff=StopModel(id="R2-D", location=(37.5219, 127.0411), service_duration=300),
            ),
        ],
    ),
)

solution = solve_request(request)
print(solution.feasible, solution.score)
for vehicle_id, stops in solution.routes.items():
    print(vehicle_id, [(stop.stop_id, stop.pickup, stop.arrival_time) for stop in stops])
print(solution.unassigned, solution.vehicle_metrics["V1"].peak_load)

같은 유스케이스를 그림과 실행 결과가 담긴 Jupyter 노트북으로도 볼 수 있습니다. examples/pickup-delivery.ipynb ↗

입력 파라미터

VehicleModel

필드 의미
id 필수 입력 차량 id입니다. capacity 필수 입력 어느 시점에든 실을 수 있는 최대 적재량입니다. home 필수 입력 출발 지점입니다. (위도, 경도)로 줍니다. departure_time 출발 시각입니다. 하루 시작부터 센 초 단위입니다. return_to_depot 출발지로 돌아오는 구간까지 계산합니다. 기본값은 꺼짐입니다. max_stops 픽업과 배송을 합친 최대 정차 수입니다. 요청 하나가 2로 계산됩니다. 기본값은 20이고, 0이면 제한이 없습니다. max_travel_time 운전 시간 한도(초)입니다. 0이면 제한이 없습니다. max_route_duration 대기와 서비스를 포함한 경로 소요 시간 한도(초)입니다. 0이면 제한이 없습니다. max_end_time 경로가 끝나야 하는 시각입니다. 0이면 제한이 없습니다. max_route_radius_meters home에서 정차 지점까지 허용하는 최대 직선거리(미터)입니다. 0이면 제한이 없습니다. min_load_ratio 사용한 차량이 달성해야 할 배송량 목표입니다. capacity 대비 비율로 줍니다. fixed_cost 이 차량을 한 번이라도 쓸 때 드는 고정 비용입니다. initial_route 경로의 시작점이 되는 정차 지점 id 목록입니다. 요청의 픽업과 배송은 둘 다 넣거나 둘 다 빼야 합니다. pinned_stops initial_route 앞쪽에서 바꿀 수 없는 정차 지점 수입니다.

StopModel

필드 의미
id 필수 입력 정차 지점 id입니다. location 필수 입력 위치입니다. (위도, 경도)로 줍니다. min_start_time 방문 시간대가 열리는 시각입니다. 하루 시작부터 센 초 단위입니다. max_end_time 방문 시간대가 닫히는 시각입니다. 하루 시작부터 센 초 단위입니다. service_duration 정차 지점에서 머무는 시간(초)입니다.

DeliveryModel

필드 의미
id 필수 입력 요청 id입니다. demand 필수 입력 픽업부터 배송까지 싣고 가는 적재량입니다. pickup 필수 입력 픽업 지점 StopModel입니다. dropoff 필수 입력 배송 지점 StopModel입니다. required_vehicle 이 요청을 꼭 태워야 하는 차량입니다. 경로에서의 위치는 자유롭습니다. order_time 요청이 들어온 시각입니다. 이미 기다리고 있었다면 음수입니다. squared_order_age_cost만 이 값을 읽습니다.

PdpInput

필드 의미
vehicles 필수 입력 차량 목록입니다. deliveries 필수 입력 운송 요청 목록입니다. driving_seconds 운전 시간 행렬입니다. 선택 사항입니다.

PdpRequest

필드 의미
model_input 필수 입력 위의 PdpInput입니다.

풀이 파라미터

풀이를 호출할 때 넘기는 값입니다. 시간 제한, 시드, 병렬 수가 여기에 있습니다.

파라미터 기본값 의미
name None 요청에 붙이는 이름입니다. 선택 사항입니다.
timelimit 30.0 탐색 시간(초)이며, 0부터 1e9까지 줄 수 있습니다.
random_seed 0 탐색에 쓰는 난수 시드입니다.
num_workers 1 독립적으로 동시에 돌리는 탐색 수입니다. 가장 좋은 결과를 고릅니다.
stop_at_first_feasible False 필수 점수가 0이 되는 즉시 멈춥니다.
solver_parameters {} SolverConfig 필드를 이름별로 담은 딕셔너리입니다. 시간 제한, 시드, 탐색 수, on_new_best는 여기서 정할 수 없습니다.
constraints None 점수에 넣을 제약과 그 설정입니다. 지정하지 않으면 기본 제약을 씁니다.
탐색 옵션 전체 (53)

solver_parameters에 이름별로 넘기세요.

파라미터 기본값 의미
acceptor_type LATE_ACCEPTANCE 이동을 받아들일지 판단하는 규칙입니다.
best_score_limit — 최고 점수가 이 값에 닿으면 일찍 멈춥니다. 기본값으로는 작동하지 않습니다.
blink_rate 0.01 복구할 때 후보 위치를 건너뛸 확률입니다. 그래서 반복 실행의 결과가 달라집니다. 0이면 쓰지 않습니다.
descent_max_sweeps 4 한 이웃을 포기하기 전까지 도는 개선 횟수입니다.
descent_weight 0.0 최선 개선 하강의 비중입니다. 0이면 끕니다.
driving_time_nearby True 운전 시간이 가까운 지점 쪽으로 이동 상대와 복구 위치를 치우치게 합니다.
driving_time_nearby_probability 0.8 그 치우침을 적용할 확률입니다.
driving_time_nearby_size 20 지점마다 유지할 이웃 수입니다.
first_fit_decreasing True 방문 시간대가 빠듯하고 수요가 큰 것부터 배치합니다. False면 입력 순서를 씁니다.
inter_exchange_max_segment 3 CROSS 교환으로 맞바꾸는 구간의 최대 길이입니다.
inter_exchange_move_weight 0.0 두 경로 사이에서 구간을 맞바꾸는 CROSS 교환의 비중입니다. 기본값은 꺼짐입니다.
late_acceptance_size 0 늦은 수락(late acceptance) 기록의 길이입니다. 0이면 문제 크기에 맞춰 정합니다.
list_swap_move_weight 0.1 목록 교환 이동의 상대적 비중입니다. 0이면 쓰지 않습니다.
on_new_best None 새 최고 해를 찾을 때마다 부르는 콜백입니다. 콜백이 예외를 내면 풀이를 멈추고 그 예외를 그대로 냅니다.
or_opt_move_weight 0.3 짧은 구간을 옮기는 Or-opt 이동의 상대적 비중입니다. 0이면 쓰지 않습니다.
pair_assignment_probability 0.1 짝 이동 가운데 요청을 빼거나 다시 넣는 이동의 비중입니다.
pair_construction_heuristic True 요청을 하나씩 온전히 넣어 시작 해를 만듭니다.
pair_exchange_min_nodes 300 그 이동을 쓰는 최소 문제 크기(정차 지점 수)입니다. 0이면 크기와 상관없이 씁니다.
pair_exchange_moves True 요청 전체를 맞바꾸는 이동을 씁니다.
pair_moves True 픽업과 배송을 하나로 다루는 이동을 씁니다.
pair_repair_probability 0.7 짝 이동 가운데 깨진 요청을 고치는 데 쓰는 비중입니다.
pair_ruin True 정차 지점 하나가 아니라 요청 전체를 파괴합니다.
parallel_solver_count 1 독립적으로 동시에 돌리는 탐색 수입니다. 탐색마다 시드가 다르고 시간은 똑같이 쓰며, 가장 좋은 결과를 고릅니다.
random_seed 0 탐색에 쓰는 난수 시드입니다.
record_to_record_end_gap 0.0 같은 차이의 탐색 종료 시점 값입니다.
record_to_record_start_gap 0.02 기록 대비 수락 방식에서 시작할 때 최고 점수 아래로 허용하는 차이입니다. 초기 목적값에 대한 비율입니다.
regret_k 3 2 이상이면 regret-k 복구를 씁니다. 0이나 1이면 단순 그리디 복구입니다.
relocate_move_weight 0.15 재배치 이동의 상대적 비중입니다. 0이면 쓰지 않습니다.
route_elimination_max_size 12 그 이동이 비우는 경로의 최대 크기입니다.
route_elimination_weight 0.0 가장 작은 경로를 다른 경로로 비우는 이동의 비중입니다. 0이면 끕니다.
route_ruin True 경로 전체를 비우는 파괴 연산자를 넣습니다.
ruin_recreate True 탐색이 정체되면 적응형 파괴·재구성을 실행합니다.
ruin_recreate_as_move_max_ruin 12 그 작은 파괴로 제거할 최대 항목 수입니다.
ruin_recreate_as_move_weight 0.0 한 걸음을 작은 파괴·복구로 쓰고 일반 이동처럼 판단할 확률입니다. 음수는 지원하는 유스케이스에서 자동 선택이고, 0이면 끕니다.
ruin_recreate_max_ruin_count 60 한 번에 제거하는 항목 수의 절대 상한입니다.
ruin_recreate_max_ruin_fraction 0.4 한 번에 제거하는 해의 최대 비율입니다.
ruin_recreate_min_ruin_fraction 0.1 한 번에 제거하는 해의 최소 비율입니다.
ruin_recreate_operator_decay 0.8 연산자 가중치가 적응하는 속도입니다.
ruin_recreate_polish_steps 5000 실행 후 다듬는 언덕 오르기 이동 수입니다. step_count_limit에는 세지 않습니다.
ruin_recreate_rewards [3.0, 2.0, 1.0, 0.5] 새 최고, 개선, 수락, 거절 결과에 주는 연산자 보상입니다.
ruin_recreate_selection_alpha 0.05 ALPHA_UCB 방식의 탐험 가중치입니다.
ruin_recreate_selection_segment_length 100 구간별 룰렛 휠 방식에서 가중치를 갱신하는 반복 수입니다.
ruin_recreate_selection_type ROULETTE_WHEEL 파괴 연산자를 고르는 방식입니다.
ruin_recreate_unimproved_step_trigger 5000 파괴·재구성을 실행하기까지 새 최고 해 없이 지나는 걸음 수입니다.
sisr_max_string_removals 3 부분 문자열 제거 한 번에 없애는 최대 문자열 수입니다.
sisr_max_string_size 12 없애는 문자열의 최대 길이입니다.
sisr_ruin True 부분 문자열 제거를 파괴 연산자에 넣습니다.
spent_limit_seconds 30.0 탐색 시간(초)이며, 0부터 1e9까지 줄 수 있습니다.
step_count_limit 0 이 걸음 수에 도달하면 멈춥니다. 0이면 제한이 없습니다.
tail_swap_move_weight 0.1 두 목록의 뒷부분을 맞바꾸는 이동(2-opt*)의 상대적 비중입니다. 0이면 쓰지 않습니다.
two_opt_move_weight 0.35 2-opt 이동의 상대적 비중입니다. 0이면 쓰지 않습니다.
unimproved_spent_limit_seconds 0.0 새 최고 해 없이 이 시간(초)이 지나면 멈춥니다. 0이면 제한이 없습니다.
unimproved_step_count_limit 0 새 최고 해 없이 이 걸음 수가 지나면 멈춥니다. 0이면 제한이 없습니다.

돌아오는 결과

solve_request는 PdpSolution을 돌려줍니다. 결정 내용은 routes와 unassigned에 있습니다.

PdpSolution

필드 의미
routes 필수 입력 차량 id별로 순서가 정해진 정차 목록입니다. 정차마다 stop_id, delivery_id, pickup, arrival_time이 있습니다. unassigned 경로에 넣지 못한 요청입니다. score 필수 입력 필수, 중간, 선호 수준으로 이루어진 문자열 점수입니다. feasible 필수 입력 필수 제약을 하나도 어기지 않으면 True입니다. total_driving_seconds 필수 입력 모든 경로의 운전 시간 합계입니다. vehicle_metrics 차량별 정차 수, 요청 수, peak_load, 배송량, 각종 시간, 경로 종료 시각입니다. 참고용이며 점수에는 들어가지 않습니다.

제약

optimaru.pickup_delivery.constraints에서 클래스를 가져와 VehicleCapacityCost()처럼 호출해서 넘깁니다. 넘긴 제약만 점수에 들어가고, 아무것도 넘기지 않으면 기본 제약을 씁니다. 목록에 같은 제약을 여러 번 넣을 수 있으며, 넣은 것마다 따로 점수에 들어갑니다. 제약마다 다음 파라미터를 받습니다.

파라미터 기본값 의미
weight None 제약 비용에 곱하는 값이며, 적용되는 수준의 단위로 셉니다. 지정하지 않으면 아래 기본 가중치를 씁니다. 기본 가중치가 0인 제약은 가중치를 줘야 작동합니다.
level None "hard", "medium", "soft"를 주면 제약을 그 수준으로 옮깁니다. Level.HARD, Level.MEDIUM, Level.SOFT도 됩니다. 지정하지 않으면 아래 수준을 그대로 씁니다. 이 유스케이스에는 중간 수준이 있어서 어느 제약이든 중간으로 옮길 수 있습니다.
exponent 1.0 부호를 유지한 채 비용에 거듭제곱을 적용하며, 0보다 커야 합니다. offset을 반영한 뒤에 적용합니다. 2.0이면 제곱이라 한곳에 몰린 위반의 비용이 크게 늘어납니다. 차량이나 날짜 같은 단위마다 적용하고, 합계 하나로 계산하는 제약에는 그 합계에 적용합니다.
offset 0.0 거듭제곱 전에 비용 x에서 빼는 값입니다. exponent처럼 단위마다, 합계로 계산하는 제약은 그 합계에 적용하며, 비용과 같은 척도(초, 분, 개수 등)로 셉니다. 부호와 상관없이 유한한 수면 되고, 키워드로만 줄 수 있습니다. 이 값 아래에서 어떻게 계산할지는 clip이 정합니다.
clip True True면 offset을 문턱값으로 씁니다. 넘은 부분만 계산하므로(max(0, x - offset) ** exponent) 그 이하의 비용은 아무것도 더하지 않습니다. False면 부호를 유지한 채 (x - offset) ** exponent를 그대로 계산하므로, 오프셋보다 작은 단위는 비용이 0이어도 음수, 곧 보상으로 들어갑니다. 하드 점수에 들어가는 수준에서는 clip=False에 0이 아닌 오프셋을 주면 ValueError가 납니다. 하드 0이 위반 없음이라는 뜻을 지키기 위해서입니다. 키워드로만 줄 수 있습니다.

중간 제약의 기본 가중치는 중간 수준 단위로 1입니다. 탐색은 중간 값에 1e9을 곱해 선호 값과 합친 점수로 해를 비교하므로, 선호 합계가 1e9보다 작은 동안에는 중간 수준이 선호보다 우선합니다. level로 어느 제약이든 세 수준 가운데 하나로 옮길 수 있습니다. level="medium"이면 중간으로 옮기고, "hard"나 "soft"면 중간 제약을 필수나 선호로 옮깁니다. 가중치는 적용되는 수준의 단위로 셉니다.

위의 최소 실행 예제에 이어서 실행합니다.

from optimaru.pickup_delivery.constraints import (
    PairedRequestCost, PickupBeforeDropoffCost, SameVehicleCost, TravelTimeCost,
    UnassignedRequestsCost, VehicleCapacityCost, get_constraints,
)

picked = get_constraints([
    PairedRequestCost(), SameVehicleCost(), PickupBeforeDropoffCost(), UnassignedRequestsCost(),
    VehicleCapacityCost(), TravelTimeCost(weight=10),
])
print(solve_request(request, constraints=picked).score)
이름 수준 기본 가중치 하는 일
vehicle_capacity_cost 필수 1 운행 중 적재량이 capacity를 넘은 만큼 벌점을 줍니다. 적재량은 픽업에서 늘고 배송에서 줄기 때문에, 경로 합계가 아니라 최고치가 기준입니다.
max_end_time_cost 필수 1 도착 시각에 서비스 시간을 더한 값이 max_end_time을 넘긴 시간(분, 올림)에 벌점을 줍니다.
travel_time_cost 선호 1 운전 시간 합계를 줄입니다. 돌아오는 구간은 return_to_depot을 켰을 때만 계산합니다.
max_travel_time_cost 필수 1 max_travel_time을 넘은 운전 시간(초)에 벌점을 줍니다.
max_route_duration_cost 필수 1 대기와 서비스를 포함한 경로 시간이 max_route_duration을 넘은 만큼(초) 벌점을 줍니다.
vehicle_max_end_time_cost 필수 1 경로 종료 시각이 max_end_time을 넘긴 시간(초)에 벌점을 줍니다.
max_stops_cost 필수 1 max_stops를 넘은 정차 수에 벌점을 줍니다. 요청 하나가 2로 계산됩니다.
max_route_radius_cost 필수 1 가장 먼 정차 지점이 출발지에서 max_route_radius_meters를 넘은 거리(미터)에 벌점을 줍니다.
enclosing_circle_radius_cost 선호 0 경로의 정차 지점을 모두 감싸는 가장 작은 원의 반지름을 줄입니다. 출발지는 빼고 계산합니다. 기본 가중치가 0이라 쓰려면 가중치를 줘야 합니다.
min_capacity_utilization_cost 선호 1 사용한 차량의 배송량이 min_load_ratio 목표에 못 미친 만큼 벌점을 줍니다.
route_duration_cost 선호 0 대기와 서비스를 포함한 경로 시간 합계를 줄입니다. 기본 가중치가 0이라 쓰려면 가중치를 줘야 합니다.
latency_cost 선호 0 출발부터 각 정차 지점 도착까지 걸린 시간의 합을 줄입니다. 기본 가중치가 0이라 쓰려면 가중치를 줘야 합니다.
squared_order_age_cost 선호 0 요청마다 order_time부터 배송이 끝날 때까지 걸린 시간(초)의 제곱을 더해 줄입니다. 기본 가중치가 0이라 쓰려면 가중치를 줘야 합니다.
vehicle_fixed_cost 선호 1 한 번이라도 쓴 차량의 fixed_cost를 더합니다.
pinned_stops_cost 필수 1e12 경로는 그 차량의 고정 정차 지점으로 순서대로 시작해야 합니다. 어긋난 정차 지점마다 한 번씩 계산합니다.
required_vehicle_cost 필수 1000 요청이 required_vehicle에 타지 않으면 벌점을 줍니다. 미배정은 한 번, 다른 차량은 두 번 계산하므로 자기 차량에 자리가 없는 요청은 배정되지 않고 기다립니다.
paired_request_cost 필수 1000 픽업과 배송 중 하나만 경로에 들어간 요청에 벌점을 줍니다.
same_vehicle_cost 필수 1000 픽업과 배송이 서로 다른 차량에 들어간 요청에 벌점을 줍니다.
pickup_before_dropoff_cost 필수 1000 경로에서 배송이 픽업보다 앞에 오는 요청에 벌점을 줍니다.
unassigned_requests_cost 중간 1 픽업과 배송 모두 경로에 없는 요청의 서비스 시간(분)을 벌점으로 줍니다.

제약 사용법 →

기존 해에서 시작하기

최신 버전이 필요합니다. pip install -U optimaru로 올려 주세요.

with_initial_solution(request, solution)은 해를 차량별 initial_route로 옮기고, 요청에 있던 값은 덮어씁니다.

위의 최소 실행 예제에 이어서 실행합니다.

from optimaru.pickup_delivery.models import with_initial_solution

seeded = with_initial_solution(request, solution)  # solution.model_dump(mode="json")도 됩니다
better = solve_request(seeded)
print(better.score, better.unassigned)
  • 완전한 해를 넣으면 구성 단계를 건너뛰고 그 해에서 바로 탐색을 시작합니다. 일부만 넣으면 넣은 부분은 그대로 두고, 빠진 요청만 새로 구성합니다.
  • unassigned에 있던 요청도 다시 배정을 시도합니다.
  • timelimit=0을 주면 바로 멈추므로 완전한 해는 넣은 그대로 돌아옵니다. step_count_limit = 0은 제한이 없다는 뜻이므로, 바로 멈추려면 시간 제한을 쓰세요.
  • 차량의 pinned_stops는 요청에 있는 값을 그대로 씁니다. 해의 경로가 그 정차 지점들로 시작하지 않으면 ValueError가 납니다.
  • 모르는 id, 두 번 나온 정차 지점, 픽업과 배송이 떨어진 요청도 ValueError를 냅니다. 그래서 짝이 깨진 불가능한 결과는 시작 해로 쓸 수 없습니다.

예외와 제한

  • VehicleModel의 max_stops는 따로 정하지 않으면 20입니다. 없애려면 0을 주세요.
  • 경로는 기본적으로 열린 경로입니다. return_to_depot을 켜지 않으면 돌아오는 구간은 계산하지 않습니다.
  • 이미 실려 있는 물건은 픽업이 남아 있지 않습니다. 차량 위치에 서비스 시간이 없는 픽업을 만들고 pinned_stops로 고정하세요.
  • 픽업을 고정하면 그 요청은 해당 차량에 남습니다. 고정 구간 뒤의 정차 지점은 순서를 바꾸거나, 다른 차량으로 옮기거나, 사이에 다른 정차 지점을 넣을 수 있습니다.
  • required_vehicle은 위치는 고정하지 않고 차량만 고정합니다. 약속된 일이지만 순서는 바꿔도 될 때 씁니다.
  • max_travel_time, max_route_duration, max_end_time, max_stops, min_load_ratio, fixed_cost, max_route_radius_meters 중 하나라도 설정하면 제약 플러그인 방식으로 풀며, 이때는 num_workers가 적용되지 않습니다.