企业官网建设流程全解析

以下为本文档的中文说明

ortools-pickup-delivery-routing 是一个基于 Google OR-Tools（Google 开源运筹优化库）的强大约束求解引擎，专门用于建模和求解带有配对约束和时间窗约束的取送货路径优化问题（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 Routing

Use 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 Flow

1. Create one pickup node and one dropoff node per job.
2. Add same-vehicle and precedence constraints for every pair.
3. Apply the customer-facing time windows and service-time convention from the problem statement.
4. Choose optional-service handling: independent pairs, or connected request sets.
5. After solving, postprocess connected sets, rebuild route sequences if needed, and re-audit feasibility before counting served jobs or writing output.

Pair Structure

• Represent 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 Times

• Apply 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 Skeleton

Use 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.

solver=routing.solver()forjobinjobs:pickup_index=manager.NodeToIndex(job.pickup_node)dropoff_index=manager.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,high=job.dropoff_window time_dimension.CumulVar(dropoff_index).SetRange(low,high)ifjob.pickup_windowisnotNone:low,high=job.pickup_window time_dimension.CumulVar(pickup_index).SetRange(low,high)

Optional And Connected Service

• First 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_cardinality=len(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:

solver=routing.solver()forjobinjobs:pickup_index=manager.NodeToIndex(job.pickup_node)dropoff_index=manager.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 Sets

For all-or-none grouped service, perform the following post-processing steps after extracting raw route order:

1. Identify connected groups whose pickup and dropoff nodes all appear in the extracted routes.
2. Keep only service stops belonging to complete groups.
3. Rebuild each remaining route by reconnecting kept stops in their original order between the route’s original start and end depot.
4. Recompute arrival times, service starts, departures, and load along the rebuilt route.
5. 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):complete=set()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 Checks

• Extract 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 Rules

• If ride time, maximum wait, or shift duration matters, add explicit constraints on the relevant time cumul variables.