Recent Releases of pyvrp
pyvrp - v0.11.1
This patch release fixes the following bugs:
- A bug where iterating over a route would segfault if the route's last trip was empty (fixed via #812);
- A bug where initial vehicle load was not respected during move evaluation (fixed via #813).
Zenodo: https://doi.org/10.5281/zenodo.15498243
Full Changelog: https://github.com/PyVRP/PyVRP/compare/v0.11.0...v0.11.1
- Python
Published by N-Wouda 9 months ago
pyvrp - v0.11.0
The 0.11.0 release of PyVRP adds support for multi-trip VRP (reloading). It additionally adds several other features, and fixes a few open issues.
Highlights
- PyVRP now supports multiple trips, with reloading at various reload depots along the route, chosen from the
VehicleType.reload_depotslist. The number of reloads can also be constrained, asVehicleType.max_reloads. See here for a quick tutorial on how to use this. - The
VehicleTypenow supports a latest start constraint, via itsVehicleType.start_lateattribute. Thanks @joopvdh!
Breaking changes
While we have updated some internals in breaking ways (e.g., #711, #713, #795), none of these are directly exposed to the user. We thus expect no difficulties upgrading to this version of PyVRP.
Additional
- The penalty weights for infeasible solutions now use floating point numbers internally, instead of integers. This resulted in a slight improvement in solution quality. See #711 for details.
- There is now one penalty weight for each load dimension, rather than a single one for all (in #713). This should result in better performance on instances with multiple load dimensions and unscaled data.
- PyVRP now makes more efficient use of memory when determining initial penalty weights and granular search neighbourhoods. This particularly matters for very large routing instances. See #730 for details. Thanks @libklein!
- Performance on instances with many different vehicle types should now be improved. See #558 for a long overview of various steps we have taken to accomplish this.
- The documentation now explains various concepts (in #695), and includes a glossary and a FAQ (in #675).
- The VehicleType can start non-empty at the start (depot) location, by setting the
VehicleType.initial_loadattribute (in #738). This is helpful when modelling routing problems where vehicles may be parked overnight, without first emptying at a depot.
Bugs fixed
- Fixed a bug where assignment to client groups was broken (in #682, also backported to the 0.10.1 release).
- Fixed a bug where
plot_resultraised when there was no feasible solution (in #725). - Fixed a bug where
SwapRouteswould always evaluate moves as non-improving (in #742). Thanks @joopvdh!
What's Changed
- Do not deref route when determining when node is a depot node by @N-Wouda in https://github.com/PyVRP/PyVRP/pull/679
- Better (dev) documentation by @N-Wouda in https://github.com/PyVRP/PyVRP/pull/675
- Fix client group bug by @N-Wouda in https://github.com/PyVRP/PyVRP/pull/682
- Make concatenation schemes default constructable by @N-Wouda in https://github.com/PyVRP/PyVRP/pull/685
- Simplify Route updates by @N-Wouda in https://github.com/PyVRP/PyVRP/pull/686
- Harden and test Route::swap by @N-Wouda in https://github.com/PyVRP/PyVRP/pull/688
- Remove index members from concatenation schemes by @N-Wouda in https://github.com/PyVRP/PyVRP/pull/687
- Forward input arguments by @N-Wouda in https://github.com/PyVRP/PyVRP/pull/695
- Simplify route segments by @N-Wouda in https://github.com/PyVRP/PyVRP/pull/690
- Add iterators and initial value to Matrix class by @N-Wouda in https://github.com/PyVRP/PyVRP/pull/696
- Reduce node internal access a bit by @N-Wouda in https://github.com/PyVRP/PyVRP/pull/697
- Simplify Exchange a little by @N-Wouda in https://github.com/PyVRP/PyVRP/pull/698
- Do not use isDepot check in Exchange by @N-Wouda in https://github.com/PyVRP/PyVRP/pull/699
- Simplify Route internal representation by @N-Wouda in https://github.com/PyVRP/PyVRP/pull/700
- Store only cumulative route distance by @N-Wouda in https://github.com/PyVRP/PyVRP/pull/701
- Support latest start on vehicle type by @joopvdh in https://github.com/PyVRP/PyVRP/pull/692
- Document model attributes and concepts by @N-Wouda in https://github.com/PyVRP/PyVRP/pull/694
- Add overlap tolerance argument to LocalSearch call by @N-Wouda in https://github.com/PyVRP/PyVRP/pull/705
- Simplify SWAP* by @N-Wouda in https://github.com/PyVRP/PyVRP/pull/706
- Link to concepts from API docs by @N-Wouda in https://github.com/PyVRP/PyVRP/pull/707
- Use standard constructs for SwapStar::ThreeBest by @N-Wouda in https://github.com/PyVRP/PyVRP/pull/708
- Simplify SWAP* a bit more by @N-Wouda in https://github.com/PyVRP/PyVRP/pull/709
- Make
CostEvaluatorpenalties doubles by @N-Wouda in https://github.com/PyVRP/PyVRP/pull/711 - Penalty per load dimension by @N-Wouda in https://github.com/PyVRP/PyVRP/pull/713
- Route schedule statistics by @N-Wouda in https://github.com/PyVRP/PyVRP/pull/716
- Faster Route::insert and Route::clear by @N-Wouda in https://github.com/PyVRP/PyVRP/pull/720
- Simplify LS loop a bit by @N-Wouda in https://github.com/PyVRP/PyVRP/pull/721
- Reduce iterations in slow tests by @N-Wouda in https://github.com/PyVRP/PyVRP/pull/722
- Fix plot_result raising when there is no feasible solution by @N-Wouda in https://github.com/PyVRP/PyVRP/pull/725
- Do not store intermediate cost matrices when determining average costs by @libklein in https://github.com/PyVRP/PyVRP/pull/731
- Add initial vehicle loads by @N-Wouda in https://github.com/PyVRP/PyVRP/pull/738
- Ensure SwapTails move is evaluated when an empty route is involved by @joopvdh in https://github.com/PyVRP/PyVRP/pull/743
- Bugfix: SwapRoutes always evaluates to zero by @joopvdh in https://github.com/PyVRP/PyVRP/pull/742
- Move check overlapping routes to SwapStar by @joopvdh in https://github.com/PyVRP/PyVRP/pull/744
- Determine underlying route from first Proposal segment by @N-Wouda in https://github.com/PyVRP/PyVRP/pull/748
- Add time windows to depot by @N-Wouda in https://github.com/PyVRP/PyVRP/pull/750
- Create Solution object in
read_solutionby @leonlan in https://github.com/PyVRP/PyVRP/pull/757 - Unrestrict Python upper constraint by @alessio-locatelli in https://github.com/PyVRP/PyVRP/pull/775
- Parallellise tests by @N-Wouda in https://github.com/PyVRP/PyVRP/pull/782
- Use perfect forwarding when creating a matrix object from data by @N-Wouda in https://github.com/PyVRP/PyVRP/pull/785
- Read HFVRP instances by @leonlan in https://github.com/PyVRP/PyVRP/pull/777
- Randomise vehicle types in applyEmptyRouteMoves by @leonlan in https://github.com/PyVRP/PyVRP/pull/787
- Reduce memory use in Solution constructor by @N-Wouda in https://github.com/PyVRP/PyVRP/pull/783
- Use a shared ptr to hold solutions by @N-Wouda in https://github.com/PyVRP/PyVRP/pull/792
- Multi-trip / reloading by @N-Wouda in https://github.com/PyVRP/PyVRP/pull/739
- Rename DurationSegment::twEarly to startEarly, twLate to startLate by @N-Wouda in https://github.com/PyVRP/PyVRP/pull/797
- Improve the tutorial a bit by @N-Wouda in https://github.com/PyVRP/PyVRP/pull/799
- Fix Route access in CVRP build mode by @N-Wouda in https://github.com/PyVRP/PyVRP/pull/802
- Fix multi-trip fleet minimisation by @N-Wouda in https://github.com/PyVRP/PyVRP/pull/803
- v0.11 benchmarks by @leonlan in https://github.com/PyVRP/PyVRP/pull/801
New Contributors
- @joopvdh made their first contribution in https://github.com/PyVRP/PyVRP/pull/692
- @libklein made their first contribution in https://github.com/PyVRP/PyVRP/pull/731
- @alessio-locatelli made their first contribution in https://github.com/PyVRP/PyVRP/pull/775
Zenodo: https://doi.org/10.5281/zenodo.15425780
Full Changelog: https://github.com/PyVRP/PyVRP/compare/v0.10.0...v0.11.0
- Python
Published by N-Wouda 9 months ago
pyvrp - v0.10.0
The 0.10.0 release of PyVRP adds support for multiple load dimensions. It additionally fixes a few open issues, and adds support for Python 3.13.
Highlights
- PyVRP now supports multiple load dimensions.
- PyVRP now has a simple fleet minimisation procedure.
Breaking changes
- As a consequence of our support for multiple load dimensions, the
Client.delivery,Client.pickup,VehicleType.capacityfields now return lists, rather than single numbers. Similarly, theexcess_load()methods onRouteandSolutionnow returns lists rather than integers. - PyVRP now requires at least one vehicle type to be passed for a valid
ProblemDatainstance.
Bugs fixed
- Fixed a bug where client release times were not respected by the route's earliest start time (in https://github.com/PyVRP/PyVRP/issues/633, also backported to the 0.9.1 release).
Additional
- PyVRP now releases the GIL when entering expensive, native operations where the GIL plays no role.
- Bumped our dependency on
pybind11to v2.13.5 (in #644). - Dropped support for Python 3.9, added support for Python 3.13 (in #663).
What's Changed
- Support reading GVRP instances ragged group data by @leonlan in https://github.com/PyVRP/PyVRP/pull/628
- Split off Solution::Route as pyvrp::Route by @N-Wouda in https://github.com/PyVRP/PyVRP/pull/630
- Fix bug related to release and start times by @N-Wouda in https://github.com/PyVRP/PyVRP/pull/635
- Add simple routine for minimising fleet size by @N-Wouda in https://github.com/PyVRP/PyVRP/pull/638
- Bump pybind11 to 2.12.0 by @N-Wouda in https://github.com/PyVRP/PyVRP/pull/643
- Bump pybind11 to v2.13.5 by @N-Wouda in https://github.com/PyVRP/PyVRP/pull/644
- Pickle the data instance by @N-Wouda in https://github.com/PyVRP/PyVRP/pull/646
- Document how to profile by @N-Wouda in https://github.com/PyVRP/PyVRP/pull/652
- Update CI build matrix by @N-Wouda in https://github.com/PyVRP/PyVRP/pull/657
- Update citation details by @N-Wouda in https://github.com/PyVRP/PyVRP/pull/658
- Support Python 3.13, drop 3.9 by @N-Wouda in https://github.com/PyVRP/PyVRP/pull/663
- Release GIL in heavy operations by @N-Wouda in https://github.com/PyVRP/PyVRP/pull/666
- Microbenchmarks in CI by @N-Wouda in https://github.com/PyVRP/PyVRP/pull/668
- Require at least one vehicle type by @leonlan in https://github.com/PyVRP/PyVRP/pull/669
- Harden workflows by @N-Wouda in https://github.com/PyVRP/PyVRP/pull/670
- Dedicated CodSpeed workflow by @N-Wouda in https://github.com/PyVRP/PyVRP/pull/672
- Multiple load dimensions by @N-Wouda and @wouterkool in https://github.com/PyVRP/PyVRP/pull/645
- Benchmarks v0.10.0 by @leonlan in https://github.com/PyVRP/PyVRP/pull/677
Zenodo: https://zenodo.org/records/14051650
Full Changelog: https://github.com/PyVRP/PyVRP/compare/v0.9.1...v0.10.0
- Python
Published by N-Wouda over 1 year ago
pyvrp - v0.9.0
The 0.9.0 release of PyVRP adds support for mixed distance and duration based objectives, different distance and duration profiles, different start and end depots on each route, and fixes an overflow bug that sometimes materialised when solving VRPs with time windows.
Highlights
- PyVRP now supports mixed distance and duration terms in the objective function. This means you are now able to optimise problems with both distance-based and duration-based costs.
- PyVRP now supports different start and end depots. This is particularly useful for re-optimisation.
- PyVRP now supports routing profiles, a flexible way to specify different distance and duration matrices for groups of vehicles. This can be used to model zone restrictions, but also account for the differences between e.g. cars, trucks, and bicycles.
Breaking changes
- We have removed the
dist()andduration()access methods from theProblemDatainstance. One should instead directly obtain the distance or duration matrices fromProblemData, and index those directly. - We have removed depot time windows. These are unnecessary since the vehicle types already have time windows, and those generalise time windows on the depots.
- We have separated the start and end depot arguments on the vehicle type. Instead of passing a single
depotargument when adding a vehicle type, now passstart_depotandend_depot. Passing the same depot to bothstart_depotandend_depotretains the previous behaviour.
Additional
- We have removed a warning about empty solutions being added to the
Population, which sometimes happens when solving instances with optional clients. This is not problematic, so the warning was not appropriate. - We have added a warning about penalty values reaching their maximum value. This typically indicates a feasibility problem in the data.
- We have added a devcontainer for PyVRP development. This should make it easier for new contributors to get started with PyVRP.
What's Changed
- Update documentation about discussion feature by @N-Wouda in https://github.com/PyVRP/PyVRP/pull/545
- Support vehicle-specific distance and duration objectives by @N-Wouda in https://github.com/PyVRP/PyVRP/pull/546
- Randomly select optional clients in Solution random constructor by @leonlan in https://github.com/PyVRP/PyVRP/pull/554
- Add profile-guided optimisation option to build script by @N-Wouda in https://github.com/PyVRP/PyVRP/pull/559
- Randomly select vehicle types/routes in Solution::makeRandom by @N-Wouda in https://github.com/PyVRP/PyVRP/pull/562
- Make repeated builds faster by splitting libcommon by @N-Wouda in https://github.com/PyVRP/PyVRP/pull/568
- Remove dist() and duration() accessors on ProblemData by @N-Wouda in https://github.com/PyVRP/PyVRP/pull/567
- Routing profiles by @N-Wouda in https://github.com/PyVRP/PyVRP/pull/573
- Update OR-Tools benchmark by @leonlan in https://github.com/PyVRP/PyVRP/pull/587
- Fix integer overflow issue in DurationSegment by @leonlan in https://github.com/PyVRP/PyVRP/pull/590
- Warn when a penalty parameter reaches its maximum value by @N-Wouda in https://github.com/PyVRP/PyVRP/pull/598
- Update and add some missing docstrings by @N-Wouda in https://github.com/PyVRP/PyVRP/pull/606
- Computed initial penalty values by @N-Wouda in https://github.com/PyVRP/PyVRP/pull/607
- Remove EmptySolutionWarning by @N-Wouda in https://github.com/PyVRP/PyVRP/pull/611
- Implement route profiles in pyvrp.search by @N-Wouda in https://github.com/PyVRP/PyVRP/pull/579
- Remove depot time windows by @N-Wouda in https://github.com/PyVRP/PyVRP/pull/616
- Fix duplicate max duration timewarp by @wouterkool in https://github.com/PyVRP/PyVRP/pull/613
- Separate start and end depots by @N-Wouda in https://github.com/PyVRP/PyVRP/pull/612
- Add summary() method to Result by @N-Wouda in https://github.com/PyVRP/PyVRP/pull/619
- Add a new example to the tutorial by @N-Wouda in https://github.com/PyVRP/PyVRP/pull/618
- PyVRP devcontainer by @leonlan in https://github.com/PyVRP/PyVRP/pull/580
- Read SDVRP instances by @leonlan in https://github.com/PyVRP/PyVRP/pull/617
Zenodo: https://doi.org/10.5281/zenodo.12568807
Full Changelog: https://github.com/PyVRP/PyVRP/compare/v0.8.2...v0.9.0
- Python
Published by N-Wouda over 1 year ago
pyvrp - v0.8.1
Small patch that fixes an issue with the automated deployment workflow.
What's Changed
- Benchmark results v0.8.0 by @leonlan in https://github.com/PyVRP/PyVRP/pull/542
- Run CD also on push to main by @N-Wouda in https://github.com/PyVRP/PyVRP/pull/544
Full Changelog: https://github.com/PyVRP/PyVRP/compare/v0.8.0...v0.8.1
- Python
Published by N-Wouda almost 2 years ago
pyvrp - v0.8.0
The second release of 2024 adds support for several new VRP variants, includes a few much needed refactorings, and overall makes PyVRP easier to use.
Highlights
- PyVRP now also supports return shipments, from clients back to the depot (in #471). This means PyVRP can now also solve the VRP with backhaul, and the VRP with simultaneous pickup and delivery. Examples have been added to the documentation (in #513).
- PyVRP now supports a maximum distance constraint (in #500), in addition to the maximum duration constraint that was added in v0.7.0.
- PyVRP now supports mutually exclusive client groups (in #514). Exactly one client in such a group must be visited. This can be used to model generalised VRP, but also for example the VRP with multiple time windows.
Model.solvenow takes solver configuration options, and can be toggled to display solver progress.
Breaking changes
The following breaking changes have been made to PyVRP's Model interface:
- The default values for
tw_lateandmax_durationhas changed toINT_MAXin all cases. Additionally,VehicleType.tw_early = 0,VehicleType.tw_late = INT_MAX, andVehicleType.max_duration = INT_MAXnow no longer takeNoneas an argument (in #463). - The
VehicleTypenow also has amax_distance = INT_MAXargument. - The
Client.demandattribute has been renamed todelivery, and aClient.pickupattribute has been added. Thepickupattribute can be used to indicate the amount of goods flowing from a client back to the depot. TheClient.__init__method has been updated to reflect these changes (in #471). More generally,demandhas been renamed todelivery, and apickupvalue has been added where appropriate. - We have separated the underlying data structures for clients and depots (in #481). Before, a depot also used the same data structure as a client, which resulted in many attributes that a depot does not have (and should not have been set to values other than zero). This change rectifies the situation by making those attributes unavailable for depots. The consequences to user code should be limited if one uses the
pyvrp.Modelinterface. - The
Clientobject now also takes an optionalgroupargument to indicate membership in a client group. - All getters have been renamed to drop the use of
get_. E.g.,solution.get_routes()is now simplysolution.routes(). - All
namearguments (available for depots, clients, and vehicle types) must now be passed as keywords, rather than by position.
Additional changes have been made to PyVRP's internals, but should not impact users of PyVRP's modelling interface.
Additional
- We have added OR-Tools as a reference solver to our benchmarks page (in #469). The gaps to the BKS are 5-13% across different instances.
- PyVRP now uses 64-bit integer values internally (in #490). This significantly increases the range of acceptable input values.
What's Changed
- Update pybind11 to v2.11.1 by @N-Wouda in https://github.com/PyVRP/PyVRP/pull/447
- Update pyvrp.repair operator interface to use lists of routes, not solutions by @N-Wouda in https://github.com/PyVRP/PyVRP/pull/448
- Add Solution::Route::depot() member by @N-Wouda in https://github.com/PyVRP/PyVRP/pull/449
- Consistency checks by @N-Wouda in https://github.com/PyVRP/PyVRP/pull/450
- Add another TWS test checking duration and time warp values by @N-Wouda in https://github.com/PyVRP/PyVRP/pull/457
- Add asserts that check for overflow by @N-Wouda in https://github.com/PyVRP/PyVRP/pull/462
- Test Client::required field is correctly set, add Client attributes documentation by @N-Wouda in https://github.com/PyVRP/PyVRP/pull/466
- Move tests out of the source tree by @N-Wouda in https://github.com/PyVRP/PyVRP/pull/467
- Make [0, INT_MAX] the default time windows by @N-Wouda in https://github.com/PyVRP/PyVRP/pull/463
- OR-Tools benchmark by @leonlan in https://github.com/PyVRP/PyVRP/pull/469
- Print solver progress by @leonlan in https://github.com/PyVRP/PyVRP/pull/460
- Proxy for segments of route statistics by @N-Wouda in https://github.com/PyVRP/PyVRP/pull/473
- New README badges by @leonlan in https://github.com/PyVRP/PyVRP/pull/477
- Simultaneous pickup and delivery by @N-Wouda in https://github.com/PyVRP/PyVRP/pull/471
- Separate client and depot structs by @N-Wouda in https://github.com/PyVRP/PyVRP/pull/481
- Rename TimeWindowSegment to DurationSegment by @N-Wouda in https://github.com/PyVRP/PyVRP/pull/483
- Remove NodeStats struct, use vectors instead by @N-Wouda in https://github.com/PyVRP/PyVRP/pull/484
- Support VRPLIB backhaul instances by @leonlan in https://github.com/PyVRP/PyVRP/pull/485
- Update read and tests to properly round load and capacity values by @N-Wouda in https://github.com/PyVRP/PyVRP/pull/493
- Switch over to int64_t by @N-Wouda in https://github.com/PyVRP/PyVRP/pull/490
- VRPB benchmarking instructions by @leonlan in https://github.com/PyVRP/PyVRP/pull/494
- Add DistanceSegment by @N-Wouda in https://github.com/PyVRP/PyVRP/pull/487
- Per client argument in CLI by @leonlan in https://github.com/PyVRP/PyVRP/pull/497
- Remove "get" prefix from data accessors by @N-Wouda in https://github.com/PyVRP/PyVRP/pull/499
- Split 2-OPT into ReverseSegment and SwapTails by @N-Wouda in https://github.com/PyVRP/PyVRP/pull/510
- Update quick tutorial with new problem variants by @N-Wouda in https://github.com/PyVRP/PyVRP/pull/513
- Remove unnecessary local search operators by @leonlan in https://github.com/PyVRP/PyVRP/pull/511
- Exact round function by @leonlan in https://github.com/PyVRP/PyVRP/pull/517
- Add support for a maximum distance constraint by @N-Wouda in https://github.com/PyVRP/PyVRP/pull/500
- Remove double precision support by @N-Wouda in https://github.com/PyVRP/PyVRP/pull/518
- Update tests to use assert_equal where possible by @N-Wouda in https://github.com/PyVRP/PyVRP/pull/519
- Make name argument keyword only by @N-Wouda in https://github.com/PyVRP/PyVRP/pull/526
- Add ClientGroup by @N-Wouda in https://github.com/PyVRP/PyVRP/pull/528
- Generalised VRP by @N-Wouda in https://github.com/PyVRP/PyVRP/pull/514
- Make collecting statistics optional by @N-Wouda in https://github.com/PyVRP/PyVRP/pull/531
- Add SolveParams configuration and separate solve function by @leonlan in https://github.com/PyVRP/PyVRP/pull/523
- Make PopulationParams fields readonly by @N-Wouda in https://github.com/PyVRP/PyVRP/pull/536
- Clip the penalty parameters to [1, 100K] by @N-Wouda in https://github.com/PyVRP/PyVRP/pull/535
- Add a link to the paper's preprint to README and docs by @N-Wouda in https://github.com/PyVRP/PyVRP/pull/540
- Simplify operators by @N-Wouda in https://github.com/PyVRP/PyVRP/pull/534
Full Changelog: https://github.com/PyVRP/PyVRP/compare/v0.7.0...v0.8.0
- Python
Published by N-Wouda almost 2 years ago
pyvrp - v0.7.0
Welcome to PyVRP 0.7! This first release of 2024 introduces several new features, some bug fixes, and overall improvements. There are also a few breaking changes, listed below.
PyVRP now supports: - Vehicle routing problems with multiple depots; - Vehicles with maximum route duration constraints; - Python 3.12.
New features
ProblemData.replaceallows one to create a newProblemDatainstance where one or more attributes are replaced with the given arguments (in #383).- Max duration constraints on
VehicleType(in #395). - Optional, free-form name fields for clients, depots, and vehicle types (in #426).
- A new aggregate
MultipleCriteriastopping criterion (in #427). This can be used to apply multiple stopping criteria at the same time. - PyVRP now supports VRPs with multiple depots (in #411).
- PyVRP now uses an ordered crossover for TSP instances (in #423).
- Support for Python 3.12 (in #413).
Breaking changes
VehicleType.__init__arguments, argument order and argument defaults have changed: see the documentation for details.- Separate
clientsanddepotsarguments inProblemData.__init__. TimeWindowSegment.total_time_warphas been renamed toTimeWindowSegment.time_warp, in line with other uses.- Removed the
TimedNoImprovementstopping criterion (in #427). Use the new aggregatepyvrp.stop.MultipleCriteriaclass instead, with argumentsNoImprovementandMaxRuntime.
Additional
- MDVRPTW benchmark instances from the literature, in VRPLIB format (in https://github.com/PyVRP/Instances/pull/6).
- PyVRP v0.7.0 drops support for Python 3.8. The supported range of Python versions going forward is Python 3.9 - 3.12.
What's Changed
- Implement ProblemData.replace by @leonlan in https://github.com/PyVRP/PyVRP/pull/383
- Keep route alive in Route::push_back and Route::insert by @leonlan in https://github.com/PyVRP/PyVRP/pull/385
- Fix neighbourhood calculation by @N-Wouda in https://github.com/PyVRP/PyVRP/pull/388
- Nearest route insert by @N-Wouda in https://github.com/PyVRP/PyVRP/pull/386
- Decouple clients/depots lists by @N-Wouda in https://github.com/PyVRP/PyVRP/pull/360
- Describe VRPLIB format by @N-Wouda in https://github.com/PyVRP/PyVRP/pull/391
- Fix typos in test_PenaltyManager.py by @wouterkool in https://github.com/PyVRP/PyVRP/pull/392
- Always apply round_func to service times; update instances by @N-Wouda in https://github.com/PyVRP/PyVRP/pull/393
- Fix random constructor vehicle usage by @leonlan in https://github.com/PyVRP/PyVRP/pull/397
- Don't re-open namespace std for specialisations by @N-Wouda in https://github.com/PyVRP/PyVRP/pull/400
- Fix build by pinning pydantic version by @N-Wouda in https://github.com/PyVRP/PyVRP/pull/402
- Bump Python version in RTD/fix dependencies by @N-Wouda in https://github.com/PyVRP/PyVRP/pull/403
- Update VEHICLE specification in docs by @N-Wouda in https://github.com/PyVRP/PyVRP/pull/405
- Reduce VehicleType struct size by @N-Wouda in https://github.com/PyVRP/PyVRP/pull/406
- Update docblock by @N-Wouda in https://github.com/PyVRP/PyVRP/pull/407
- Add homepage link to package metadata by @N-Wouda in https://github.com/PyVRP/PyVRP/pull/409
- Remove superfluous compile flag in TWS by @N-Wouda in https://github.com/PyVRP/PyVRP/pull/410
- Add support for Python 3.12, drop Python 3.8 by @N-Wouda in https://github.com/PyVRP/PyVRP/pull/413
- Add max duration support by @N-Wouda in https://github.com/PyVRP/PyVRP/pull/395
- Update type hinting to use builtin list, dict, and tuple by @N-Wouda in https://github.com/PyVRP/PyVRP/pull/418
- Multi depot by @N-Wouda in https://github.com/PyVRP/PyVRP/pull/411
- Add a flag that tracks whether the Route's structure has updated, but statistics have not been synced yet by @N-Wouda in https://github.com/PyVRP/PyVRP/pull/421
- Add OX for TSP by @N-Wouda in https://github.com/PyVRP/PyVRP/pull/423
- Add TspWarning to the docs by @N-Wouda in https://github.com/PyVRP/PyVRP/pull/424
- Add support for reading MDVRPTW instances by @N-Wouda in https://github.com/PyVRP/PyVRP/pull/425
- Add name fields by @N-Wouda in https://github.com/PyVRP/PyVRP/pull/426
- Write MDVRPTW solutions, enable benchmarking by @N-Wouda in https://github.com/PyVRP/PyVRP/pull/427
- Fix multi-depot test by @leonlan in https://github.com/PyVRP/PyVRP/pull/431
- Link to Python source code by @leonlan in https://github.com/PyVRP/PyVRP/pull/382
- Enforce zero matrix diagonal by @wouterkool in https://github.com/PyVRP/PyVRP/pull/436
- Update docs about MDVRPTW by @N-Wouda in https://github.com/PyVRP/PyVRP/pull/432
- Citation metadata by @N-Wouda in https://github.com/PyVRP/PyVRP/pull/398
- Add missing default none for optional argument in _pyvrp.pyi by @wouterkool in https://github.com/PyVRP/PyVRP/pull/437
- Add benchmark results to docs by @N-Wouda in https://github.com/PyVRP/PyVRP/pull/438
Full Changelog: https://github.com/PyVRP/PyVRP/compare/v0.6.3...v0.7.0
- Python
Published by N-Wouda about 2 years ago
pyvrp - v0.6.3
Bugfix release that adds evaluation of fixed vehicle cost differences to the TwoOpt operator.
What's Changed
- Fix docstring num vehicle types by @leonlan in https://github.com/PyVRP/PyVRP/pull/379
- Improve operator evaluation by @N-Wouda in https://github.com/PyVRP/PyVRP/pull/376
- Evaluate fixed costs in TwoOpt by @leonlan in https://github.com/PyVRP/PyVRP/pull/381
Full Changelog: https://github.com/PyVRP/PyVRP/compare/v0.6.2...v0.6.3
- Python
Published by N-Wouda over 2 years ago
pyvrp - v0.6.2
Adds the extract_docstrings.py script to the source distribution (sdist).
What's Changed
- Add test fixtures for instance reading by @N-Wouda in https://github.com/PyVRP/PyVRP/pull/372
- Add LS test for required clients by @N-Wouda in https://github.com/PyVRP/PyVRP/pull/370
- Add extract_docstrings script to sdist by @N-Wouda in https://github.com/PyVRP/PyVRP/pull/377
Full Changelog: https://github.com/PyVRP/PyVRP/compare/v0.6.1...v0.6.2
- Python
Published by N-Wouda over 2 years ago
pyvrp - v0.6.1
Patch release that fixes a bug in TwoOpt, which did not work correctly with different vehicle types.
What's Changed
- Add v0.6.0 link in docs by @N-Wouda in https://github.com/PyVRP/PyVRP/pull/367
- Benchmark v0.6.0 by @leonlan in https://github.com/PyVRP/PyVRP/pull/368
- Fix bug in TwoOpt by @N-Wouda in https://github.com/PyVRP/PyVRP/pull/369
Full Changelog: https://github.com/PyVRP/PyVRP/compare/v0.6.0...v0.6.1
- Python
Published by N-Wouda over 2 years ago
pyvrp - v0.6.0
This release adds support for additional VRP attributes, a few bug fixes, and improved interoperability between Python and PyVRP's native extensions.
Highlights
- We have improved the support for different vehicle types in PyVRP. In particular, the
pyvrp.VehicleTypeobject now supports different vehicle costs, as well as shifts. - PyVRP now has rudimentary support for ruin-and-recreate algorithms. We have updated our local search method to work with incomplete, ruined solutions, and implemented a new greedy repair operator available in
pyvrp.repair.
What's Changed
- Make Route::Node prev/next attributes private, anticipating removal by @N-Wouda in https://github.com/PyVRP/PyVRP/pull/316
- Move data from Route::Node to Route by @N-Wouda in https://github.com/PyVRP/PyVRP/pull/314
- Move route modification to Route by @N-Wouda in https://github.com/PyVRP/PyVRP/pull/319
- Some profiling stuff by @N-Wouda in https://github.com/PyVRP/PyVRP/pull/321
- Add depots to Route::nodes by @N-Wouda in https://github.com/PyVRP/PyVRP/pull/320
- Make Node client, idx, and route fields private by @N-Wouda in https://github.com/PyVRP/PyVRP/pull/323
- Make Client of type
size_tby @wouterkool in https://github.com/PyVRP/PyVRP/pull/322 - Test Route and Route::Node by @N-Wouda in https://github.com/PyVRP/PyVRP/pull/324
- Add test checking node properties update when interacting with routes by @N-Wouda in https://github.com/PyVRP/PyVRP/pull/326
- Move route update into LS::update by @N-Wouda in https://github.com/PyVRP/PyVRP/pull/327
- Move TWS data from Route::Node to Route by @N-Wouda in https://github.com/PyVRP/PyVRP/pull/325
- Improve docs and bind operator funcs by @N-Wouda in https://github.com/PyVRP/PyVRP/pull/333
- Fix tests for macOS by @leonlan in https://github.com/PyVRP/PyVRP/pull/310
- Import/export by @N-Wouda in https://github.com/PyVRP/PyVRP/pull/336
- BugFix:
Solution::operator==for unassigned clients by @wouterkool in https://github.com/PyVRP/PyVRP/pull/317 - Simplify SWAP* by @wouterkool in https://github.com/PyVRP/PyVRP/pull/302
- Pickle support for Solution and Solution::Route by @N-Wouda in https://github.com/PyVRP/PyVRP/pull/337
- Simplify cli by @N-Wouda in https://github.com/PyVRP/PyVRP/pull/339
- Add a SWAP* test that checks in-place swaps by @N-Wouda in https://github.com/PyVRP/PyVRP/pull/340
- Cast Matrix/np.ndarray by @N-Wouda in https://github.com/PyVRP/PyVRP/pull/338
- Documentation fixes by @N-Wouda in https://github.com/PyVRP/PyVRP/pull/342
- Make returned matrix non-writeable by @N-Wouda in https://github.com/PyVRP/PyVRP/pull/346
- Improve rng by @N-Wouda in https://github.com/PyVRP/PyVRP/pull/347
- Test descriptions by @N-Wouda in https://github.com/PyVRP/PyVRP/pull/349
- Add page with some guidelines and experiences implementing new VRP variants in PyVRP by @N-Wouda in https://github.com/PyVRP/PyVRP/pull/350
- Test within route two opt by @N-Wouda in https://github.com/PyVRP/PyVRP/pull/351
- Fix wrong load difference evaluation in SWAP* by @N-Wouda in https://github.com/PyVRP/PyVRP/pull/353
- Cast measure by @N-Wouda in https://github.com/PyVRP/PyVRP/pull/356
- Allow incomplete solutions in LS by @N-Wouda in https://github.com/PyVRP/PyVRP/pull/354
- Simplify cli by @leonlan in https://github.com/PyVRP/PyVRP/pull/357
- Greedy repair operator by @N-Wouda in https://github.com/PyVRP/PyVRP/pull/312
- Remove params/attributes from API reference TOC by @leonlan in https://github.com/PyVRP/PyVRP/pull/363
- Fixed cost vehicle types by @N-Wouda in https://github.com/PyVRP/PyVRP/pull/359
- Shift time windows by @N-Wouda in https://github.com/PyVRP/PyVRP/pull/364
Full Changelog: https://github.com/PyVRP/PyVRP/compare/v0.5.0...v0.6.0
- Python
Published by N-Wouda over 2 years ago
pyvrp - v0.5.0
This release contains no major new features, but it simplifies the internal workings of PyVRP quite a bit and fixes a few bugs.
What's Changed
- Use Solution string representation in Result string representation by @leonlan in https://github.com/PyVRP/PyVRP/pull/269
- Update notebooks by @N-Wouda in https://github.com/PyVRP/PyVRP/pull/266
- Add exceptions and warnings to documentation by @N-Wouda in https://github.com/PyVRP/PyVRP/pull/279
- Add VehicleType depot field and use that in places by @N-Wouda in https://github.com/PyVRP/PyVRP/pull/274
- Collect statistics by default by @N-Wouda in https://github.com/PyVRP/PyVRP/pull/280
- Route overhaul by @N-Wouda in https://github.com/PyVRP/PyVRP/pull/281
- Allow empty node/route operator lists in LS by @N-Wouda in https://github.com/PyVRP/PyVRP/pull/286
- Remove intensifyonbest and intensify_probability by @N-Wouda in https://github.com/PyVRP/PyVRP/pull/287
- Document GeneticAlgorithmParams by @N-Wouda in https://github.com/PyVRP/PyVRP/pull/288
- Move docstrings into C++ by @N-Wouda in https://github.com/PyVRP/PyVRP/pull/291
- Bugfix: compute offsets for vehicle types correctly in LocalSeach by @wouterkool in https://github.com/PyVRP/PyVRP/pull/292
- Some fixes for CodeCheck/clang-tidy warnings by @N-Wouda in https://github.com/PyVRP/PyVRP/pull/294
- Remove circle sector by @N-Wouda in https://github.com/PyVRP/PyVRP/pull/251
- SearchMethod protocol by @N-Wouda in https://github.com/PyVRP/PyVRP/pull/297
- Allow incomplete solutions by @N-Wouda in https://github.com/PyVRP/PyVRP/pull/301
- Rename XorShift128 to RandomNumberGenerator by @N-Wouda in https://github.com/PyVRP/PyVRP/pull/308
- Use TWS for route timing statistics computation by @wouterkool in https://github.com/PyVRP/PyVRP/pull/241
- Validate arguments in ProblemData by @leonlan in https://github.com/PyVRP/PyVRP/pull/306
- Add Evaluatable concept by @N-Wouda in https://github.com/PyVRP/PyVRP/pull/304
- Allow empty local search neighbourhoods by @leonlan in https://github.com/PyVRP/PyVRP/pull/309
- Remove delta reversal distance attribute by @N-Wouda in https://github.com/PyVRP/PyVRP/pull/313
- Implement LocalSearch.call in C++ by @N-Wouda in https://github.com/PyVRP/PyVRP/pull/298
Full Changelog: https://github.com/PyVRP/PyVRP/compare/v0.4.4...v0.5.0
- Python
Published by N-Wouda over 2 years ago
pyvrp - v0.4.3
What's Changed
Several changes to the internal PyVRP structure.
- Add dynamic bitset by @N-Wouda in https://github.com/PyVRP/PyVRP/pull/256
- Per-folder extension module by @N-Wouda in https://github.com/PyVRP/PyVRP/pull/262
- Rename _common to _pyvrp by @N-Wouda in https://github.com/PyVRP/PyVRP/pull/263
- Namespaces by @N-Wouda in https://github.com/PyVRP/PyVRP/pull/264
- Remove using namespace directives by @N-Wouda in https://github.com/PyVRP/PyVRP/pull/265
Full Changelog: https://github.com/PyVRP/PyVRP/compare/v0.4.2...v0.4.3
- Python
Published by N-Wouda over 2 years ago
pyvrp - v0.4.0
Highlights
- Support for heterogeneous vehicle capacities.
- Support for client release times.
- A simpler modelling interface in the form of
pyvrp.Model. - Various documentation and performance improvements.
What's Changed
- Logos in README and docs by @N-Wouda in https://github.com/PyVRP/PyVRP/pull/225
- Simplify SREX by @N-Wouda in https://github.com/PyVRP/PyVRP/pull/228
- Explicit cost, distance, and duration types by @N-Wouda in https://github.com/PyVRP/PyVRP/pull/210
- Speed up greedyRepair, improve deltaCost evaluation by @N-Wouda in https://github.com/PyVRP/PyVRP/pull/232
- Add support for double precision by @N-Wouda in https://github.com/PyVRP/PyVRP/pull/234
- Base route angle on centroid of client locations by @N-Wouda in https://github.com/PyVRP/PyVRP/pull/237
- Remove C++ LS dependency on rng, use separate shuffle method by @N-Wouda in https://github.com/PyVRP/PyVRP/pull/238
- Simpler modelling interface by @N-Wouda in https://github.com/PyVRP/PyVRP/pull/236
- Only store non-empty routes in Individual by @wouterkool in https://github.com/PyVRP/PyVRP/pull/240
- Remove distances and prizes from Individual string representation by @leonlan in https://github.com/PyVRP/PyVRP/pull/243
- Introduction to VRP and HGS documentation by @leonlan in https://github.com/PyVRP/PyVRP/pull/242
- Rename Individual to Solution by @N-Wouda in https://github.com/PyVRP/PyVRP/pull/246
- Rename pyvrp.educate to pyvrp.search by @N-Wouda in https://github.com/PyVRP/PyVRP/pull/248
- Heterogeneous vehicle type by @wouterkool in https://github.com/PyVRP/PyVRP/pull/245
- Release times by @leonlan in https://github.com/PyVRP/PyVRP/pull/254
Full Changelog: https://github.com/PyVRP/PyVRP/compare/v0.3.0...v0.4.0
- Python
Published by N-Wouda over 2 years ago
pyvrp - v0.3.0
Prize-collecting!
- Add PyVRP/Instances submodule by @N-Wouda in https://github.com/PyVRP/PyVRP/pull/216
- Route object by @N-Wouda in https://github.com/PyVRP/PyVRP/pull/221
- Prize-collecting by @N-Wouda in https://github.com/PyVRP/PyVRP/pull/213
- Prizes in neighbourhood calculation by @N-Wouda in https://github.com/PyVRP/PyVRP/pull/223
- Add prizes to Individual str output by @N-Wouda in https://github.com/PyVRP/PyVRP/pull/224
Full Changelog: https://github.com/PyVRP/PyVRP/compare/v0.2.1...v0.3.0
- Python
Published by N-Wouda almost 3 years ago
pyvrp - v0.2.0
TL;DR: Lots of quality of life changes, and further improvements to the codebase since the initial release of PyVRP a few months ago.
What's Changed
- Rename "Feasible objectives" to just "Objectives" in plot title by @N-Wouda in https://github.com/PyVRP/PyVRP/pull/161
- Reduce coupling by @N-Wouda in https://github.com/PyVRP/PyVRP/pull/162
- Initial submission configs by @leonlan in https://github.com/PyVRP/PyVRP/pull/160
- Individual.make_random by @N-Wouda in https://github.com/PyVRP/PyVRP/pull/165
- Remove args from clang-format in pre-commit by @leonlan in https://github.com/PyVRP/PyVRP/pull/167
- GA should reject empty populations by @N-Wouda in https://github.com/PyVRP/PyVRP/pull/172
- Reduce coupling in Population and GA now takes initial solutions by @leonlan in https://github.com/PyVRP/PyVRP/pull/168
- Deterministic C++ implementation of SREX by @leonlan in https://github.com/PyVRP/PyVRP/pull/175
- Remove PenaltyManager state from LS operators by @N-Wouda in https://github.com/PyVRP/PyVRP/pull/177
- Remove vehicle capacity from penaltymanager by @wouterkool in https://github.com/PyVRP/PyVRP/pull/186
- Implement CostEvaluator by @wouterkool in https://github.com/PyVRP/PyVRP/pull/200
- Move route sorting inside SREX by @wouterkool in https://github.com/PyVRP/PyVRP/pull/202
- Generalise binary tournament by @N-Wouda in https://github.com/PyVRP/PyVRP/pull/183
- Separate distance and duration matrices by @N-Wouda in https://github.com/PyVRP/PyVRP/pull/209
- BugFix: loadIndividual sets depot TWdata to zero by @wouterkool in https://github.com/PyVRP/PyVRP/pull/211
- Initialize ProblemData with list of Clients by @wouterkool in https://github.com/PyVRP/PyVRP/pull/206
- Sort granular neighbourhood by proximity by @N-Wouda in https://github.com/PyVRP/PyVRP/pull/214
- Benchmarks for v0.2.0 by @N-Wouda in https://github.com/PyVRP/PyVRP/pull/220
Full Changelog: https://github.com/PyVRP/PyVRP/compare/v0.1.0...v0.2.0
- Python
Published by N-Wouda almost 3 years ago
pyvrp - v0.1.0
First public release
PyVRP is a Python package that implements Hybrid Genetic Search as a state-of-the-art Vehicle Routing Problem (VRP) solver. The package is designed for the VRP with Time Windows (VRPTW), but can be easily extended to support other VRP variants. PyVRP combines the flexibility of Python with the performance of C++, by implementing performance critical parts of the algorithm in C++, while being fully customisable at the Python level. PyVRP is a polished implementation of the algorithm that ranked 1st in the 2021 DIMACS VRPTW Challenge and, after improvements, ranked 1st on the static variant of the EURO Meets NeurIPS 2022 Vehicle Routing Competition. The code follows good software engineering practices, and is well-documented and unit tested. PyVRP is freely available under the liberal MIT license.
- Python
Published by N-Wouda almost 3 years ago