Skip to content

Latest commit

 

History

History
366 lines (293 loc) · 24.1 KB

README.md

File metadata and controls

366 lines (293 loc) · 24.1 KB

Packvium for Python

Deterministic 3D bin packing and cartonization in pure Python. No runtime dependencies, and exact integer geometry instead of floats.

Use it to pick the smallest carton for an order, build a pallet, load a shipping container, or load a truck within its axle ratings and delivery-stop order. Every answer comes back as coordinates and rotations for each item, with a reason for anything that did not fit.

Version 1.11.0 — the public API is frozen. Field names, status codes and the objective vector do not change without a major version, so any 1.x is a safe upgrade from any earlier 1.x. Read docs/GUARANTEES.md before relying on a result.

Install

pip install packvium

Python 3.9 or newer. Nothing else is installed with it.

Quick start

from packvium import Container, Dimensions, Item, Packer, PackingConfig

result = Packer(PackingConfig.balanced()).pack(
    items=[Item.create("book", Dimensions.mm("210", "140", "30"), quantity=4)],
    containers=[Container.create("box", Dimensions.mm("400", "300", "250"))],
)

print(result.status.value)                # feasible
for container in result.containers:
    for placement in container.placements:
        print(placement.instance.id, placement.position, placement.rotation.value)

The same request as JSON, through the function every Packvium engine shares, or through the command line, which reads a request on standard input:

from packvium import pack_from_dict

result = pack_from_dict({
    "items": [{"id": "book", "quantity": 4, "dimensions": {"length": "210", "width": "140", "height": "30"}}],
    "containers": [{"id": "box", "inner_dimensions": {"length": "400", "width": "300", "height": "250"}}],
})
echo '{"items":[{"id":"box","quantity":8,"dimensions":{"length":"50","width":"50","height":"50"}}],
       "containers":[{"id":"carton","inner_dimensions":{"length":"100","width":"100","height":"100"}}]}' \
  | python -m packvium

The result is the same in both forms: status, the containers that were opened with a placement for every unit, and unpacked_items with a reason for each item left out.

Using it in your project

Two examples are written the way application code is written, with your own product and order records on one side and the library call in the middle. Start from the one closer to what you are building.

You are building Start from What it does
A checkout or cart page checkout.py Maps a cart onto a request, picks the cheapest cartons, and reads the parcels back for the page. Two functions hold everything Packvium-specific.
A warehouse or fulfilment job fulfilment.py Runs an order from paid to labelled: a shipping rule picks the carrier service, the order is packed under its constraints, validate checks the plan, and every parcel is priced from a pinned tariff.
An HTTP endpoint that packs errors.py Turns each kind of refused request into a 422 that names the item and the value.
A dock or driver screen execution.py, trucking.py Turns a result into numbered loading steps, and loads a van by stop and axle rating.

Rules that most projects need on day one:

  • An item that does not fit is not an error. The result lists it in unpacked_items with a reason, and everything else is still packed.
  • Support is not required by default: minimum_support_ratio is 0, so an item may rest on nothing above the container floor, and the result then says so in warnings (unsupported_placements: N placement(s) rest on nothing above the container floor; ...). To require support, set it above 0: PackingConfig.balanced(minimum_support_ratio=0.75), or "configuration": {"minimum_support_ratio": 0.75} in JSON.
  • Set an effort_budget for any answer you store or show twice. See Getting the same answer every time.

Errors

A request that no engine may answer raises packvium.InvalidRequestError, a ValueError, before anything is solved. It names the problem instead of describing it:

from packvium import InvalidRequestError, pack_from_dict

try:
    result = pack_from_dict(request)
except InvalidRequestError as error:
    error.code     # "invalid_request"
    error.reason   # "below_minimum"
    error.field    # "/items/0/quantity" -- a JSON Pointer into your request
    str(error)     # "invalid_request: /items/0/quantity: must be at least 1"

reason is one of missing_field, wrong_type, below_minimum, above_maximum, negative_measure, invalid_unit, duplicate_id, not_allowed or invalid_value. FixedPlacementError is a subclass, with code invalid_fixed_placement and reason malformed or cannot_hold. The message is the same in every Packvium engine. Branch on reason and field; show the message to a person.

An unknown objective or access_directions value in a request is refused with reason not_allowed and the JSON Pointer of the bad value (direct domain model constructors raise UnknownObjectiveError or InvalidDirectionError). A request that is valid but does not fit completely is not an error: the result lists what was left out, and why, in unpacked_items. errors.py turns all of these into HTTP responses.

Checking a result

New in 1.7.0.

packvium.validate checks a result against the request it answers, from the JSON documents alone: geometry, support and load, accounting, the result's facts and its score. It is the reference validator every Packvium package exports a port of, so they all return the same issues, code and detail:

from packvium import MalformedResult, pack_from_dict, validate

issues = validate(request, pack_from_dict(request))  # [] -- valid
for issue in issues:
    print(issue.code, issue.detail)  # e.g. collision cube#1 with cube#2 in box#1

It shares no code with the engine, so it judges any engine's result, not only this package's. A result without the documented shape raises MalformedResult, whose kind is contract or shape.

Units

Lengths are stored in ticks of 1/16000 mm and weights in ticks of 1/8 µg, as integers. Inputs are integers or decimal strings with a unit (mm, cm, m, in, ft; mg, g, kg, oz, lb), and fractional inches are exact, not approximated:

Dimensions.inches("12 3/8", "8 1/2", "3/4")
Item.create("mug", Dimensions.mm("100", "100", "120"), "12 oz")

A JSON request refuses a float measure rather than rounding it: send "160.5", not 160.5. Its units sets only the length unit; a weight takes its unit from the measure or is grams; any other units key, weight included, is refused. See docs/UNITS-AND-NUMERICS.md.

Getting the same answer every time

The search runs several starts and keeps the best. By default a wall clock decides when it stops (time_limit_ms, one second), so a search the clock cuts short keeps whatever it had reached, and a busy machine can reach less. The same request can then give a different answer on a different run.

For an answer you can store, compare or replay, bound the search by counted work instead, and keep the time limit only as a generous fuse:

from packvium import EffortBudget, PackingConfig

config = PackingConfig.balanced(
    time_limit_ms=60_000,
    effort_budget=EffortBudget(max_candidates_evaluated=50_000),
)
# JSON: "configuration": {"time_limit_ms": 60000, "effort_budget": {"max_candidates_evaluated": 50000}}

The result says what stopped the search: result.termination.code is complete, effort_limit (reproducible), or time_limit (not reproducible). replay_level(result.to_dict()), imported with from packvium.artifacts import replay_level (a submodule import packvium does not load), gives the same verdict as exact or not_guaranteed. reproducibility.py shows four simulated machines giving four different answers under a clock, and one answer under a budget.

effort_limit means the budget stopped work the search still had: a search that finishes on exactly its budget reads complete, and under a budget time_limit_ms is one fuse for the whole solve, not a slice per start. termination.any_start_truncated says whether the budget cut a start that might have won.

Solver profiles

solver_profile (JSON) or the matching PackingConfig constructor picks how hard the search tries:

Profile What it runs
fast One ordering, one solver. No runners-up.
balanced (default) Several solvers over several item orderings, keeping up to two runners-up.
quality More solvers and orderings, a beam over container choices, and exact search for small orders. Slower.
exact_small Bounded exact search when the order has at most exact_item_limit items (7, counting quantity); otherwise the same search as balanced.

The JSON path and the PackingConfig constructors share a profile's solvers but not all of its defaults. A JSON request defaults to 1 second, 8 item orderings (1 under fast) and alternatives: 3 (ranked answers, the winner included) whatever the profile. PackingConfig.fast(), .balanced(), .quality() and .exact_small() default to 0.2, 1, 5 and 10 seconds; .fast() keeps 1 ranked answer, and .quality() runs 24 orderings and keeps 5, so "solver_profile": "quality" in JSON searches less than PackingConfig.quality() unless you set multi_start_orders, alternatives and time_limit_ms to match. An effort_budget makes any of them reproducible.

Trucks, axles and delivery routes

A container can describe a vehicle, not only a box:

  • axles: [front, rear], each a position along the length and a max_load. Every placement is checked against both ratings using the gross load, tare included, and the result reports the exact axle_reactions.
  • access_directions: the walls cargo leaves through, such as ["+x"] for rear doors.
  • stop_index on an item: the stop it is delivered at, 0 first. Nothing due later may sit on top of something due earlier, or, when access_directions is set, block its last way out.

After the solve, safe_route_removal_order gives an unloading order stop by stop, replay_loading_order checks the reverse as a loading order, and placement_reachability says what can be reached when the doors open. An item the axle ratings cannot carry even alone in the vehicle is reported as axle_overloaded. See trucking.py.

Examples

Runnable, in examples/, and included in the source distribution. Each one is a single file you can read top to bottom. Every one of them is executed by the test suite on each release, so none of them can quietly stop working.

New here? Read basic.py, then objectives.py. Between them they cover what most callers need, and checkout.py shows the same call inside a project. units.py and serialization.py explain the two design choices that surprise people. extensions.py is last on purpose: reach for it only after the fields in constraints.py and limits.py have failed you.

File What it shows
checkout.py A shop's checkout: a cart mapped onto a request and the parcels read back, with the cheapest cartons chosen.
fulfilment.py An order from paid to labelled: a policy rule picks the service, the order is packed under its constraints, validate checks the plan, and each parcel is priced from a pinned tariff.
basic.py The smallest useful call: items in, placements out, and the three details in it that are easy to miss.
objectives.py Six of the seven objectives (all but maximum_volume) on scenes where they disagree, including the rate card that makes the heavier shipment the cheaper one, a rate card's currency, and the lower bound that proves the value left behind is the least possible.
constraints.py Upright-only, floor-only, non-stackable, top-load limits, and tags that keep two items out of the same box, plus how to read the reason an item was refused, and a crate allowed past the pallet deck by pallet_overhang_limit.
limits.py A courier fleet: a van with a fridge unit and wheel arches as obstacles, an item cap per bike, one dangerous-goods item per van, frozen goods only in a refrigerated vehicle, and a cap on vehicles.
units.py Why there are no floats anywhere: fractional inches, exact ticks, and the one-tick difference between a fit and a refusal.
serialization.py The same request as JSON, the result in full, and exactly which mistakes are refused and which are silently ignored.
errors.py A web handler: refused requests turned into a 422 with a pointer and a message a person can act on, fixed placements that cannot hold, and a partial fit that is not an error.
reproducibility.py Why a clock-limited search answers differently on a busy machine, how an effort budget fixes it, and how to read termination.
trucking.py A three-stop delivery van within its axle ratings: loading and unloading order, what the driver can reach at each stop, and the same goods packed without a route.
fixed_placements.py A trailer that arrives partly loaded: new pallets packed around the ones already on board, a record of what is on board that cannot be true, and a loaded pallet fixed by quoting its placement_id.
rebalancing.py Two pallets of very different weight evened out after packing, one validated move at a time.
shapes.py Items that are not their box: complementary wedges sharing one crate as convex_hull, two copies of one wedge that need a signed rotation such as -L-W+H, a cushion that compresses under load until the crush limit refuses it, and a gusseted bag that holds a layer more than a flat one.
nested.py Units into cartons, cartons onto a pallet, in one call, and level_beam_width letting the pallet pick a dearer carton set that packs better.
commerce.py Rate a shipment, apply an eligibility rule, and pin a catalog version.
execution.py Turn a result into dock instructions: solver facts kept apart from screen text, a step order that is injected or absent, and an operator lock that yields a second plan rather than editing the approved one.
artifacts.py Hand a result to a system with no engine: one document with the plan, geometry and the request that produced it, exported as CSV and a printable work order, with its replay level.
revisions.py Replan a half-loaded job: a missing item and a locked placement recorded against the approved plan, a replan that keeps the locked item in place, a hash-chained record that notices an edit, and a box already cut to measure (with a void-fill reserve) stocked for the replan.
intelligence.py Prove a carton change is worth publishing: two scenarios compared order by order, a proposal that refuses to exist on thin evidence, and a replay against held-out history where a cheaper packing your validator rejects still counts as a regression.
extensions.py A rule the schema has no field for, and an account of what you give up by writing one.

With packvium installed, run any of them from a copy of the examples/ directory:

python3 examples/trucking.py

From a checkout of the repository without installing, point Python at the source tree instead: PYTHONPATH=src python3 examples/trucking.py.

What it covers

  • Exact arithmetic. Length is measured in ticks of 1/16000 mm and weight in 1/8 µg, so no coordinate is a float and no placement depends on rounding.
  • Constraints: weight and payload limits, permitted rotations, keep-upright, floor-only, non-stackable, top-load limits, minimum support ratio, tag incompatibility, eligible container tags, per-container item and tag limits, clearance, obstacles, two-axle load limits, multi-stop route order, pallet overhang past the deck, and flat or gusseted bags.
  • Several solvers, chosen by problem shape and profile: regular-grid, layer, extreme-point, maximal-space and bounded exact search.
  • Every solution is re-validated by logic independent of the search. Unplaced items come back with a reason code. Every placement carries a placement_id that a fixed placement, a revision or a lock can quote.
  • A proof, or the distance to one. Under the default, lowest_cost, maximum_value, open_dimension_height and maximum_volume objectives every result states optimality.lower_bound. A complete result that attains it reports optimal, which proves no packing obeying the request's rules scores better; any other carries the gap to the bound (gap_key, absolute_gap, relative_gap).
  • Deterministic when you ask for it. The same request with an effort_budget gives the same result on every run and machine. A search stopped by time_limit_ms keeps what it reached, which can differ between runs; termination says which happened.
  • Multi-container and nested packing. NestedPacker(level_beam_width=K) carries the K best carton sets up a level, so the pallet decides between them, and rebalance_weight evens out the payload across containers afterwards.
  • Your own constraints, item orderings, candidate scorers, container selectors or complete solvers, registered in process.
  • Work orders. packvium.execution turns a validated result into a plan: solver facts kept apart from the text that cites them, an injected loading order or a plain unavailable, and a canonical form four engines emit byte for byte. packvium.locks lets an operator pin a placement and get a second plan beside the approved one.
  • Artifacts a warehouse system can use without an engine. packvium.artifacts wraps the plan with geometry, display values and provenance, including the request itself and its replay level. packvium.artifact_exports writes it as RFC 8785 JSON, CSV or a self-contained HTML work order, byte for byte what the other engines write.
  • Items already in place, and replanning around them. fixed_placements pins items to known positions before the solve: they keep their place, carry weight and support, and come back marked fixed: true. packvium.revisions records what changed on the dock (a missing item, a substituted container, a lock, a verification) as an append-only chain linked by SHA-256, and derives the request the next plan solves. packvium.revision_outcomes feeds those events to the historical evaluation (Python only).
  • Deciding before you publish a catalog change. packvium.simulation and packvium.recommendations compare two catalog scenarios order by order and propose a change only when the paired cohort supports it; packvium.holdout replays that proposal against history it has not seen. Python only, and signature-frozen since 1.10.0 like the packing surface. See PUBLIC-API.md.

Documentation

Document Covers
docs/GUARANTEES.md What is promised and what is not. Start here.
docs/PUBLIC-API.md Inputs, outputs and status semantics.
docs/COMMERCE-API.md Carrier rating, eligibility rules and catalog versions.
docs/UNITS-AND-NUMERICS.md Units, accepted input forms, rounding policy.

The constraint reference and the benchmarks are at packvium.com.

The Packvium family

One request and result contract, implemented independently in four engines (Rust, Python, PHP, JavaScript) and checked against each other on a shared fixture set. Python and PHP are held to byte-identical canonical results; Rust and the JavaScript fallback are held to independent validity and a per-fixture objective floor. Pick the package for your stack; mixing them in one system is safe.

Package Install Source
Python — packvium pip install packvium packvium-python
PHP — packvium/packvium composer require packvium/packvium packvium-php
Rust — packvium packvium = "1.11" packvium-rust
Node.js — @packvium/engine npm install @packvium/engine packvium-node
Browser / WebAssembly — @packvium/browser npm install @packvium/browser packvium-wasm
PHP FFI bridge — packvium/native-bridge composer require packvium/native-bridge packvium-php-bridge
Python native selector — packvium-native from source until the native wheels ship packvium-python-adapter

Contributing

See CONTRIBUTING.md. Security reports go through the process in SECURITY.md, not public issues.

Citation

If Packvium supports your research, cite it as software. GitHub's Cite this repository button reads CITATION.cff, and codemeta.json carries the same record in CodeMeta form.

@software{packvium_python,
  author  = {{Packvium contributors}},
  title   = {Packvium for Python},
  version = {1.11.0},
  license = {MIT},
  url     = {https://packvium.com}
}

License

MIT. See LICENSE.