vrp_bin_packing - Experimental¶

Warning

Possible server crash

These functions might create a server crash

Warning

Experimental functions

They are not officially of the current release.
They likely will not be officially be part of the next release:
- The functions might not make use of ANY-INTEGER and ANY-NUMERICAL
- Name might change.
- Signature might change.
- Functionality might change.
- pgTap tests might be missing.
- Might need c/c++ coding.
- May lack documentation.
- Documentation if any might need to be rewritten.
- Documentation examples might need to be automatically generated.
- Might need a lot of feedback from the comunity.
- Might depend on a proposed function of vrpRouting
- Might depend on a deprecated function of vrpRouting

Availability

Version 0.4.0

New experimental function
- vrp_knapsack

Description¶

The bin packing problem is an optimization problem, in which items of different sizes must be packed into a finite number of bins or containers, each of a fixed given capacity, in a way that minimizes the number of bins used. The problem has many applications, such as filling up containers, loading trucks with weight capacity constraints, creating file backups in media and technology mapping in FPGA semiconductor chip design.

Signatures¶

vrp_bin_packing(
  Weights SQL, bin_capacity ANY-INTEGER, [, max_rows])

RETURNS SET OF
(bin_number, item_id)

Parameters¶

Parameter	Type	Description
Weights SQL	`TEXT`	Weights SQL query describing the weight of each item
Bin_Capacity	`ANY-INTEGER`	Maximum Capacity of the bin.

Optional Parameters¶

Parameter	Type	Default	Description
max_rows	`ANY-INTEGER`	\(100000\)	Maximum items(rows) to fetch from bin_packing_data table

Inner Queries¶

Weights SQL¶

A SELECT statement that returns the following columns:

id, weight

Column	Type	Default	Description
id	`ANY-INTEGER`		unique identifier of the item.
weight	`ANY-INTEGER`		weight of the item.

Result Columns¶

Returns set of

(bin_number, item_id)

Column	Type	Description
bin_number	`ANY-INTEGER`	Integer to uniquely identify a bin
item_id	`ANY-INTEGER`	Integer to uniquely identify an item in the bin

Example¶

SELECT *
FROM bin_packing_query;
 id | weight 
----+--------
  1 |     48
  2 |     30
  3 |     19
  4 |     36
  5 |     36
  6 |     27
  7 |     42
  8 |     42
  9 |     36
 10 |     24
 11 |     30
(11 rows)

SELECT * 
FROM vrp_bin_packing('SELECT id, weight FROM bin_packing_query', 100);
 bin_number | item_id 
------------+---------
          1 |       1
          1 |       2
          1 |       3
          2 |       4
          2 |       5
          2 |       6
          3 |       7
          3 |       8
          4 |       9
          4 |      10
          4 |      11
(11 rows)

vrpRouting Manual (0.4-dev)