以下为本文档的中文说明ortools-pickup-delivery-routing 是一个基于 Google OR-ToolsGoogle 开源运筹优化库的强大约束求解引擎专门用于建模和求解带有配对约束和时间窗约束的取送货路径优化问题PDPTW, Pickup and Delivery Problem with Time Windows的专业路由优化技能。PDPTW 是组合优化和运筹学领域中最经典和最具实际应用价值的 NP-hard 问题之一其核心是在满足一系列复杂约束条件下找到一组成本最优的车辆行驶路径方案。使用场景包括在物流和快递配送行业中优化快递员的取件和送货路径确保每个包裹的取件和配送由同一车辆执行且满足客户预约的时间窗要求在共享出行平台的实时拼车和网约车调度系统中规划乘客的接送顺序和车辆路线在辅助客运服务Paratransit / Dial-a-Ride / 门到门交通服务中为行动不便的老年人或残障人士调度和规划专业的门到门接送车辆路线在同城即时配送即时零售和外卖配送平台的智能派单和骑手路线规划引擎中嵌入高效的路由求解能力。核心特点包括利用 Google OR-Tools 的 Routing Library路由库和 CP-SAT约束规划求解器将现实世界中的取送货路径问题精确地建模为约束求解数学模型在模型中灵活地定义和组合多种实际业务约束条件时间窗约束Time Window Constraints为每个取货地点和送货地点指定最早服务时间和最晚服务时间的允许范围、车辆容量约束Vehicle Capacity Constraints确保每辆车的瞬时装载量不超过其最大载重或容积限制、配对约束Pairing Constraints / Pickup and Delivery Coupling强制规定属于同一个运输订单的取货操作和送货操作必须由同一辆车辆完成且先取后送提供车辆行驶距离矩阵Distance Matrix和路段通行时间矩阵Travel Time Matrix的自动计算或外部接入方案支持使用 OpenStreetMap 的 OSRM 路由引擎或商业地图服务如 Google Maps API、高德地图 API的实时路况数据提供丰富的可调求解参数调优指南以在求解速度Solution Speed和求解质量Solution Quality / Optimality Gap之间取得适合特定业务场景的最佳平衡点支持以可视化的方式如在地图上绘制车辆路线轨迹、生成甘特图展示各车辆任务时间线展示求解出的最优路线方案并提供关键评估指标数据总行驶距离、总行驶时间、车辆使用数量、时间窗违反统计等。Pickup And Delivery RoutingUse this skill when each job has related pickup and dropoff or delivery events that must be served together. Apply it after the base routing model has a time dimension and before solving.Implementation FlowCreate one pickup node and one dropoff node per job.Add same-vehicle and precedence constraints for every pair.Apply the customer-facing time windows and service-time convention from the problem statement.Choose optional-service handling: independent pairs, or connected request sets.After solving, postprocess connected sets, rebuild route sequences if needed, and re-audit feasibility before counting served jobs or writing output.Pair StructureRepresent pickup and dropoff as separate service nodes connected by a shared job ID.Pickup demand is positive; dropoff demand is negative. Depot nodes have zero demand and zero service time.Addrouting.AddPickupAndDelivery(pickup_index, dropoff_index)for each pair.Add explicit constraints for the actual business rules:same vehicle:routing.VehicleVar(pickup_index) routing.VehicleVar(dropoff_index)pickup before dropoff:time_dimension.CumulVar(pickup_index) time_dimension.CumulVar(dropoff_index)Time Windows And Service TimesApply customer time windows to the service event promised to the customer. Appointment and dial-a-ride problems often constrain dropoff arrival; pickup windows can be derived by subtracting direct pickup-to-dropoff travel time from the dropoff window.If a problem statement gives explicit pickup and dropoff time-window formulas, implement those formulas directly. Service time belongs in the time transit from a node to the next node; do not change the stated window formula to compensate for service time unless the problem explicitly says to.Pair Constraint SkeletonUse this pattern after adding the time dimension. It enforces the paired-service relationship for each job. Add optional-service logic separately after deciding whether jobs are independent pairs or members of connected request sets.solverrouting.solver()forjobinjobs:pickup_indexmanager.NodeToIndex(job.pickup_node)dropoff_indexmanager.NodeToIndex(job.dropoff_node)routing.AddPickupAndDelivery(pickup_index,dropoff_index)solver.Add(routing.VehicleVar(pickup_index)routing.VehicleVar(dropoff_index))solver.Add(time_dimension.CumulVar(pickup_index)time_dimension.CumulVar(dropoff_index))ifjob.dropoff_windowisnotNone:low,highjob.dropoff_window time_dimension.CumulVar(dropoff_index).SetRange(low,high)ifjob.pickup_windowisnotNone:low,highjob.pickup_window time_dimension.CumulVar(pickup_index).SetRange(low,high)Optional And Connected ServiceFirst decide whether each optional job is independent or belongs to a connected request set. Independent jobs may be skipped on their own; connected request sets should be optimized as a group.For connected request sets, prefer the CP-style grouped disjunction pattern below when search quality matters. Treat it as a search-friendly relaxation: local search may keep partial groups, and postprocessing enforces the final all-or-none business rule.Some domains connect multiple pickup-delivery pairs for one passenger, order, shipment, or care plan. This is a special case: apply all-or-none handling only when the problem says a connected set must be fully served or fully rejected.For CP-style optional connected sets, put the set’s pickup nodes in one disjunction withmax_cardinalitylen(request_set)and a very large group penalty, such aslen(request_set) * request_penalty. This makes pickup service drive the served-job objective for the connected set.Add each corresponding dropoff node as optional with zero penalty. The pickup-delivery constraints still tie feasible served pairs together, while zero-penalty dropoff optionality avoids forcing orphan dropoffs when a pickup or connected set is skipped.Use this grouped-disjunction-plus-postprocessing pattern instead of hard equality constraints across the connected set when local search quality matters. Hard all-or-none constraints can make insertion and local search much harder on large optional pickup-delivery instances.This grouped-disjunction pattern may allow partial connected sets during search. If the domain treats partial connected sets as unserved, do not count partial sets as served; remove their service nodes and rebuild the route order, or reject the candidate if rebuilding breaks feasibility.The complete modeling shape for connected optional pickup-delivery service is:solverrouting.solver()forjobinjobs:pickup_indexmanager.NodeToIndex(job.pickup_node)dropoff_indexmanager.NodeToIndex(job.dropoff_node)routing.AddPickupAndDelivery(pickup_index,dropoff_index)solver.Add(routing.VehicleVar(pickup_index)routing.VehicleVar(dropoff_index))solver.Add(time_dimension.CumulVar(pickup_index)time_dimension.CumulVar(dropoff_index))forrequest_setinconnected_request_sets:pickup_indices[manager.NodeToIndex(job.pickup_node)forjobinrequest_set]routing.AddDisjunction(pickup_indices,len(request_set)*request_penalty,len(request_set),)forjobinjobs:routing.AddDisjunction([manager.NodeToIndex(job.dropoff_node)],0)Postprocessing Connected SetsFor all-or-none grouped service, perform the following post-processing steps after extracting raw route order:Identify connected groups whose pickup and dropoff nodes all appear in the extracted routes.Keep only service stops belonging to complete groups.Rebuild each remaining route by reconnecting kept stops in their original order between the route’s original start and end depot.Recompute arrival times, service starts, departures, and load along the rebuilt route.Reject the rebuilt route if a shortcut arc is invalid, a service window is missed, the vehicle cannot return to the depot in time, or final load is nonzero.defcomplete_group_job_ids(groups,visited_nodes):completeset()forgroupingroups:# group jobs expose job_id, pickup_node, and dropoff_node.ifall(job.pickup_nodeinvisited_nodesandjob.dropoff_nodeinvisited_nodesforjobingroup):complete.update(str(job.job_id)forjobingroup)returncompletedefkept_service_nodes(route,complete_job_ids):return[stop.nodeforstopinroute.stopsifstop.kindin{pickup,dropoff}andstr(stop.job_id)incomplete_job_ids]After filtering, audit the rebuilt sequence from scratch; do not reuse arrival times, loads, shortcut feasibility, depot-return feasibility, or served counts from the unfiltered route.Final ChecksExtract the route order and verify every counted job has both pickup and dropoff on the same route, with pickup before dropoff.Verify no dropoff appears without its pickup, and no pickup is counted without its dropoff.For connected request sets, count the set only when all jobs in the set pass the paired-service check.When the requested output is route-only, write only the requested route fields; leave derived timing, load, violation counts, and objective summaries out if the verifier will recompute them.Ride RulesIf ride time, maximum wait, or shift duration matters, add explicit constraints on the relevant time cumul variables.
以下为本文档的中文说明ortools-pickup-delivery-routing 是一个基于 Google OR-ToolsGoogle 开源运筹优化库的强大约束求解引擎专门用于建模和求解带有配对约束和时间窗约束的取送货路径优化问题PDPTW, Pickup and Delivery Problem with Time Windows的专业路由优化技能。PDPTW 是组合优化和运筹学领域中最经典和最具实际应用价值的 NP-hard 问题之一其核心是在满足一系列复杂约束条件下找到一组成本最优的车辆行驶路径方案。使用场景包括在物流和快递配送行业中优化快递员的取件和送货路径确保每个包裹的取件和配送由同一车辆执行且满足客户预约的时间窗要求在共享出行平台的实时拼车和网约车调度系统中规划乘客的接送顺序和车辆路线在辅助客运服务Paratransit / Dial-a-Ride / 门到门交通服务中为行动不便的老年人或残障人士调度和规划专业的门到门接送车辆路线在同城即时配送即时零售和外卖配送平台的智能派单和骑手路线规划引擎中嵌入高效的路由求解能力。核心特点包括利用 Google OR-Tools 的 Routing Library路由库和 CP-SAT约束规划求解器将现实世界中的取送货路径问题精确地建模为约束求解数学模型在模型中灵活地定义和组合多种实际业务约束条件时间窗约束Time Window Constraints为每个取货地点和送货地点指定最早服务时间和最晚服务时间的允许范围、车辆容量约束Vehicle Capacity Constraints确保每辆车的瞬时装载量不超过其最大载重或容积限制、配对约束Pairing Constraints / Pickup and Delivery Coupling强制规定属于同一个运输订单的取货操作和送货操作必须由同一辆车辆完成且先取后送提供车辆行驶距离矩阵Distance Matrix和路段通行时间矩阵Travel Time Matrix的自动计算或外部接入方案支持使用 OpenStreetMap 的 OSRM 路由引擎或商业地图服务如 Google Maps API、高德地图 API的实时路况数据提供丰富的可调求解参数调优指南以在求解速度Solution Speed和求解质量Solution Quality / Optimality Gap之间取得适合特定业务场景的最佳平衡点支持以可视化的方式如在地图上绘制车辆路线轨迹、生成甘特图展示各车辆任务时间线展示求解出的最优路线方案并提供关键评估指标数据总行驶距离、总行驶时间、车辆使用数量、时间窗违反统计等。Pickup And Delivery RoutingUse this skill when each job has related pickup and dropoff or delivery events that must be served together. Apply it after the base routing model has a time dimension and before solving.Implementation FlowCreate one pickup node and one dropoff node per job.Add same-vehicle and precedence constraints for every pair.Apply the customer-facing time windows and service-time convention from the problem statement.Choose optional-service handling: independent pairs, or connected request sets.After solving, postprocess connected sets, rebuild route sequences if needed, and re-audit feasibility before counting served jobs or writing output.Pair StructureRepresent pickup and dropoff as separate service nodes connected by a shared job ID.Pickup demand is positive; dropoff demand is negative. Depot nodes have zero demand and zero service time.Addrouting.AddPickupAndDelivery(pickup_index, dropoff_index)for each pair.Add explicit constraints for the actual business rules:same vehicle:routing.VehicleVar(pickup_index) routing.VehicleVar(dropoff_index)pickup before dropoff:time_dimension.CumulVar(pickup_index) time_dimension.CumulVar(dropoff_index)Time Windows And Service TimesApply customer time windows to the service event promised to the customer. Appointment and dial-a-ride problems often constrain dropoff arrival; pickup windows can be derived by subtracting direct pickup-to-dropoff travel time from the dropoff window.If a problem statement gives explicit pickup and dropoff time-window formulas, implement those formulas directly. Service time belongs in the time transit from a node to the next node; do not change the stated window formula to compensate for service time unless the problem explicitly says to.Pair Constraint SkeletonUse this pattern after adding the time dimension. It enforces the paired-service relationship for each job. Add optional-service logic separately after deciding whether jobs are independent pairs or members of connected request sets.solverrouting.solver()forjobinjobs:pickup_indexmanager.NodeToIndex(job.pickup_node)dropoff_indexmanager.NodeToIndex(job.dropoff_node)routing.AddPickupAndDelivery(pickup_index,dropoff_index)solver.Add(routing.VehicleVar(pickup_index)routing.VehicleVar(dropoff_index))solver.Add(time_dimension.CumulVar(pickup_index)time_dimension.CumulVar(dropoff_index))ifjob.dropoff_windowisnotNone:low,highjob.dropoff_window time_dimension.CumulVar(dropoff_index).SetRange(low,high)ifjob.pickup_windowisnotNone:low,highjob.pickup_window time_dimension.CumulVar(pickup_index).SetRange(low,high)Optional And Connected ServiceFirst decide whether each optional job is independent or belongs to a connected request set. Independent jobs may be skipped on their own; connected request sets should be optimized as a group.For connected request sets, prefer the CP-style grouped disjunction pattern below when search quality matters. Treat it as a search-friendly relaxation: local search may keep partial groups, and postprocessing enforces the final all-or-none business rule.Some domains connect multiple pickup-delivery pairs for one passenger, order, shipment, or care plan. This is a special case: apply all-or-none handling only when the problem says a connected set must be fully served or fully rejected.For CP-style optional connected sets, put the set’s pickup nodes in one disjunction withmax_cardinalitylen(request_set)and a very large group penalty, such aslen(request_set) * request_penalty. This makes pickup service drive the served-job objective for the connected set.Add each corresponding dropoff node as optional with zero penalty. The pickup-delivery constraints still tie feasible served pairs together, while zero-penalty dropoff optionality avoids forcing orphan dropoffs when a pickup or connected set is skipped.Use this grouped-disjunction-plus-postprocessing pattern instead of hard equality constraints across the connected set when local search quality matters. Hard all-or-none constraints can make insertion and local search much harder on large optional pickup-delivery instances.This grouped-disjunction pattern may allow partial connected sets during search. If the domain treats partial connected sets as unserved, do not count partial sets as served; remove their service nodes and rebuild the route order, or reject the candidate if rebuilding breaks feasibility.The complete modeling shape for connected optional pickup-delivery service is:solverrouting.solver()forjobinjobs:pickup_indexmanager.NodeToIndex(job.pickup_node)dropoff_indexmanager.NodeToIndex(job.dropoff_node)routing.AddPickupAndDelivery(pickup_index,dropoff_index)solver.Add(routing.VehicleVar(pickup_index)routing.VehicleVar(dropoff_index))solver.Add(time_dimension.CumulVar(pickup_index)time_dimension.CumulVar(dropoff_index))forrequest_setinconnected_request_sets:pickup_indices[manager.NodeToIndex(job.pickup_node)forjobinrequest_set]routing.AddDisjunction(pickup_indices,len(request_set)*request_penalty,len(request_set),)forjobinjobs:routing.AddDisjunction([manager.NodeToIndex(job.dropoff_node)],0)Postprocessing Connected SetsFor all-or-none grouped service, perform the following post-processing steps after extracting raw route order:Identify connected groups whose pickup and dropoff nodes all appear in the extracted routes.Keep only service stops belonging to complete groups.Rebuild each remaining route by reconnecting kept stops in their original order between the route’s original start and end depot.Recompute arrival times, service starts, departures, and load along the rebuilt route.Reject the rebuilt route if a shortcut arc is invalid, a service window is missed, the vehicle cannot return to the depot in time, or final load is nonzero.defcomplete_group_job_ids(groups,visited_nodes):completeset()forgroupingroups:# group jobs expose job_id, pickup_node, and dropoff_node.ifall(job.pickup_nodeinvisited_nodesandjob.dropoff_nodeinvisited_nodesforjobingroup):complete.update(str(job.job_id)forjobingroup)returncompletedefkept_service_nodes(route,complete_job_ids):return[stop.nodeforstopinroute.stopsifstop.kindin{pickup,dropoff}andstr(stop.job_id)incomplete_job_ids]After filtering, audit the rebuilt sequence from scratch; do not reuse arrival times, loads, shortcut feasibility, depot-return feasibility, or served counts from the unfiltered route.Final ChecksExtract the route order and verify every counted job has both pickup and dropoff on the same route, with pickup before dropoff.Verify no dropoff appears without its pickup, and no pickup is counted without its dropoff.For connected request sets, count the set only when all jobs in the set pass the paired-service check.When the requested output is route-only, write only the requested route fields; leave derived timing, load, violation counts, and objective summaries out if the verifier will recompute them.Ride RulesIf ride time, maximum wait, or shift duration matters, add explicit constraints on the relevant time cumul variables.
