Home > Mobile >  Algorithm for maximizing shipping profit with limitations on mass and cost
Algorithm for maximizing shipping profit with limitations on mass and cost

Time：10-23

The title isn't very helpful, because I'm not sure what I'm trying to say exactly. I'm sure an algorithm for this must exist, but I can't remember. Note: not a homework problem, I finished school a very long time ago.

So here's the problem:

  • We're doing a shipping and trading job, trying to maximize profits
  • We have a list of items that we can ship in a truck. Each item has:
    • A buy price (at the source)
    • A sell price (at the destination)
    • A per-unit mass
    • An upper limit on how many can be purchased
  • Our truck is limited in the amount of mass it can carry
  • We have an upper limit on how much we're allowed to "invest" (spend on items at the source).
  • We want to maximize the profit for our job (buy at the source, transport, sell at the destination).

If there were only one limit (total mass, or total investment), it would be easy, but I'm not sure how to approach this when there are two.

The equation for calculating profit would be:

profit = ItemA['quantity'] * (ItemA['sell_price'] - ItemA['buy_price'])   ItemB['quantity'] * (ItemB['sell_price'] - ItemB['buy_price'])   ...

So I'm trying to choose which items, and the quantity of each item, that should be purchased in order to maximize the profit.

Are there any existing, known algorithms for solving this? Likely some sort of mathematical optimization problem? I'm using Python, so I'm thinking that the mystic package might be appropriate, but I'm not sure how I'd configure it.

CodePudding user response：

You can try the framework optuna for hyperparameter tuning.

Here is an example code that you can try. My example products are apples and oranges etc. Data are just assumptions, just plugin your buy/sell prices and truck, purchase limits and others.

In parameters.json file you can input your product names, limits, buy/sell prices and others. high_weight_additional_cost is amount per kg. Sampler can be "tpe" or "cmaes". Trucks to use is added.

parameters.json

{
    "sampler": "tpe",
    "trials": 1000,
    "max_purchase": 3000,
    "min_weight_no_cost_kg": 1000,
    "high_weight_additional_cost": 0.5,
    "trucks": {
        "smalltruck": {
            "maxkg": 300,
            "cost": 75
        },
        "mediumtruck": {
            "maxkg": 600,
            "cost": 150
        },
        "bigtruck": {
            "maxkg": 1000,
            "cost": 400
        }
    },
    "products": {
        "apple_kg": {
            "min": 20,
            "max": 200,
            "buyprice": 5,
            "sellprice": 8
        },
        "oranges_kg": {
            "min": 20,
            "max": 200,
            "buyprice": 6,
            "sellprice": 10
        },
        "banana_kg": {
            "min": 20,
            "max": 200,
            "buyprice": 4,
            "sellprice": 6
        },
        "avocado_kg": {
            "min": 20,
            "max": 200,
            "buyprice": 7,
            "sellprice": 10
        },
        "Mango_kg": {
            "min": 20,
            "max": 200,
            "buyprice": 5,
            "sellprice": 8
        },
        "Pears_kg": {
            "min": 20,
            "max": 200,
            "buyprice": 5,
            "sellprice": 7
        },
        "Raspberries_kg": {
            "min": 20,
            "max": 200,
            "buyprice": 8,
            "sellprice": 12
        }
    }
}

Code

"""
shipping_trading.py


version 0.4.0
    * Add truck size optimization. It is contrained by the cost of using truck size as well as the max kg capacity.
      The optimizer may suggest a medium instead of a big truck if profit is higher as big truck is expensive.
      profit = profit - truck_cost - other_costs
    * Modify parameters.json file, trucks key is added.

version 0.3.0
    * Read sampler, and number of trials from parameters.json file.
      User inputs can now be processed from that file.


version 0.2.0
    * Read a new parameters.json format.
    * Refactor get_parameters().


version 0.1.0
    * Add additional cost if total product weight is high.
"""


import json

import optuna


def get_parameters():
    """
    Read parameters.json file to get the parameters to optimize, etc.
    """
    fn = 'parameters.json'
    parlist, parameters, category = [], {}, {}

    with open(fn) as json_file:
        values = json.load(json_file)

        sampler = values.get('sampler', "tpe")
        trials = values.get('trials', 100)
        max_purchase = values.get('max_purchase', None)
        min_weight_no_cost_kg = values.get('min_weight_no_cost_kg', None)
        high_weight_additional_cost = values.get('high_weight_additional_cost', None)

        products = values.get('products', None)
        for k, v in products.items():
            parlist.append({'name': k, 'min': v['min'], 'max': v['max'], 'buyprice': v['buyprice'], 'sellprice': v['sellprice']})

        trucks = values.get('trucks', None)
        for k, v in trucks.items():
            category.update({k: {'maxkg': v['maxkg'], 'cost': v['cost']}})

    for p in parlist:
        parameters.update({p['name']: [p['min'], p['max'], p['buyprice'], p['sellprice']]})

    return (parameters, category, sampler, trials, max_purchase, min_weight_no_cost_kg, high_weight_additional_cost)


def objective(trial):
    """
    Maximize profit.
    """
    gp = get_parameters()
    (parameters, category, _, _, max_purchase,
        min_weight_no_cost_kg, high_weight_additional_cost) = gp

    # Ask the optimizer what value we will try.
    new_param = {}    
    for k, v in parameters.items():
        suggested_value = trial.suggest_int(k, v[0], v[1])  # get suggested value from sampler
        new_param.update({k: [suggested_value, v[2], v[3]]})  # name: [suggested_value, buyprice, sellprice]

    # Choose truck size.
    # smaller is cheaper but has a low capacity
    # while bigger is expensive but has a high capacity.
    truck_data = {}
    for k, v in category.items():
        truck_data.update({k: [v['maxkg'], v['cost']]})

    # Ask the sampler which truck to use, small, medium ....
    truck_max_kg, truck_cost = None, None
    if len(truck_data):
        truck = trial.suggest_categorical("truck", list(truck_data.keys()))

        # Define truck limits based on suggested truck size.
        truck_max_kg = truck_data[truck][0]
        truck_cost = truck_data[truck][1]

    # If total wt or total amount is exceeded, we return a 0 profit.
    total_wt, total_buy, profit = 0, 0, 0
    for k, v in new_param.items():
        total_wt  = v[0]  # sum of suggested values for products
        total_buy  = v[0] * v[1]  # suggested_value * buyprice
        profit  = v[0] * (v[2] - v[1])  # suggested_value x (sellprice - buyprice)

    # (1) Truck kg limit
    if truck_max_kg is not None:
        if total_wt > truck_max_kg:
            return 0

    # (2) Purchase limit amount
    if max_purchase is not None:
        if total_buy > max_purchase:
            return 0

    # Cost for higher transport weight
    cost_high_weight = 0
    if min_weight_no_cost_kg is not None and high_weight_additional_cost is not None:
        excess_weight = total_wt - min_weight_no_cost_kg
        if excess_weight > 0:
            cost_high_weight  = (total_wt - min_weight_no_cost_kg) * high_weight_additional_cost

    # Cost for using a truck, can be small, medium etc.
    cost_truck_usage = 0
    if truck_cost is not None:
        cost_truck_usage  = truck_cost

    # Total cost
    total_cost = cost_high_weight   cost_truck_usage
    
    # Adjust profit
    profit = profit - total_cost

    # Send this profit to optimizer so that it will consider this value
    # in its optimization algo and would suggest a better value next time we ask again.
    return profit


def main():
    # Read parameters.json file for user data input.
    gp = get_parameters()
    (parameters, category, optsampler, num_trials,
        max_purchase, _, _) = gp

    # Available samplers to use:
    # https://optuna.readthedocs.io/en/stable/reference/samplers.html
    # https://optuna.readthedocs.io/en/stable/reference/generated/optuna.integration.SkoptSampler.html
    # https://optuna.readthedocs.io/en/stable/reference/generated/optuna.integration.BoTorchSampler.html
    if optsampler.lower() == 'cmaes':
        sampler = optuna.samplers.CmaEsSampler(n_startup_trials=1, seed=100)
    elif optsampler.lower() == 'tpe':
        sampler = optuna.samplers.TPESampler(n_startup_trials=10, multivariate=False, group=False, seed=100, n_ei_candidates=24)
    else:
        print(f'Warning, {optsampler} is not supported, we will be using tpe sampler instead.')
        optsampler = 'tpe'
        sampler = optuna.samplers.TPESampler(n_startup_trials=10, multivariate=False, group=False, seed=100, n_ei_candidates=24)

    study = optuna.create_study(sampler=sampler, direction='maximize')
    study.optimize(objective, n_trials=num_trials)

    # Show summary and best parameter values to maximize profit.
    print()
    print(f'sampler: {optsampler}')
    print(f'trials: {num_trials}')
    print()

    print(f'Max Purchase usd: {max_purchase}')
    # print(f'Max Truck Capacity Kg: {max_weight_kg}')
    print()

    print('Parameters being optimized:')
    for k, v in parameters.items():
        # print(f'{k}: {v}')
        print(f'{k}: {{minkg: {v[0]}, maxkg: {v[1]}, buyprice: {v[2]}, sellprice: {v[3]}}}')
    for k, v in category.items():
        print(f'{k}: {v}')
    print()

    print(f'best parameter value: {study.best_params}')
    print(f'best profit usd: {study.best_trial.values[0]}')
    print(f'best trial number out of {num_trials}: {study.best_trial.number}')
    

if __name__ == '__main__':
    main()

Output

sampler: tpe
trials: 1000

Max Purchase usd: 3000

Parameters being optimized:
apple_kg: {minkg: 20, maxkg: 200, buyprice: 5, sellprice: 8}
oranges_kg: {minkg: 20, maxkg: 200, buyprice: 6, sellprice: 10}
banana_kg: {minkg: 20, maxkg: 200, buyprice: 4, sellprice: 6}
avocado_kg: {minkg: 20, maxkg: 200, buyprice: 7, sellprice: 10}
Mango_kg: {minkg: 20, maxkg: 200, buyprice: 5, sellprice: 8}
Pears_kg: {minkg: 20, maxkg: 200, buyprice: 5, sellprice: 7}
Raspberries_kg: {minkg: 20, maxkg: 200, buyprice: 8, sellprice: 12}
smalltruck: {'maxkg': 300, 'cost': 75}
mediumtruck: {'maxkg': 600, 'cost': 150}
bigtruck: {'maxkg': 1000, 'cost': 400}

best parameter value: {'apple_kg': 170, 'oranges_kg': 200, 'banana_kg': 23, 'avocado_kg': 20, 'Mango_kg': 53, 'Pears_kg': 23, 'Raspberries_kg': 42, 'truck': 'mediumtruck'}
best profit usd: 1639.0
best trial number out of 1000: 518

If you increase the number of trials the program might be able to find a more profitable parameter values.

CodePudding user response：

Another option is by using scipy. The sample below contains 3 products, that can be scaled of course. The constrains are the purchase and max truck mass.

code

"""
shipping_trading_solver.py

Ref: https://docs.scipy.org/doc/scipy/reference/generated/scipy.optimize.minimize.html#scipy.optimize.minimize
"""


from scipy.optimize import minimize


# Constants
sell = [8, 7, 10]
buys = [6, 5, 6]

purchase_limit = 1000
truck_mass_limit = 70


def objective(x):
    """
    objective, return value as negative to maximize.
    """
    profit = 0
    for v, s, b in zip(x, sell, buys):
        profit  = v * (s - b)

    return -profit


def purchase_cons(x):
    """
    Used for constrain
    """
    purchases = 0
    for v, b in zip(x, buys):
        purchases  = v * b
    
    return purchase_limit - purchases  # not negative


def mass_cons(x):
    """
    Used for constrain
    """
    mass = 0
    for v in x:
        mass  = v
    
    return truck_mass_limit - mass  # not negative


def main():
    # Define constrained. Note: ineq=non-negative, eq=zero
    cons = (
        {'type': 'ineq', 'fun': purchase_cons},
        {'type': 'ineq', 'fun': mass_cons}
    )

    # Bounds or limits of mass per product, (min,max)
    bound = ((10, 50), (5, 20), (10, 30))

    # Initial values
    init_values = (1, 1, 3)

    # Start minimizing
    # SLSQP = Sequential Least Squares Programming
    res = minimize(objective, init_values, method='SLSQP', bounds=bound, constraints=cons)

    # Show summary
    print('Results summary:')
    print(f'optimization message: {res.message}')
    print(f'success status: {res.success}')
    print(f'profit: {-res.fun:0.2f}')
    print(f'best param values: {res.x}')
    print()

    # Verify results
    print('Verify purchase and mass limits:')

    # (1) purchases
    total_purchases = 0    
    for product_mass, buy in zip(res.x, buys):
        total_purchases  = product_mass * buy
    assert total_purchases <= purchase_limit
    print(f'actual total_purchases: {total_purchases:0.0f}, purchase_limit: {purchase_limit}')

    # (2) mass
    total_mass = 0    
    for product_mass in res.x:
        total_mass  = product_mass
    assert total_mass <= truck_mass_limit
    print(f'actual total_mass: {total_mass:0.0f}, truck_mass_limit: {truck_mass_limit}')


if __name__ == '__main__':
    main()

output

Results summary:
optimization message: Optimization terminated successfully
success status: True
profit: 200.00
best param values: [22.5 17.5 30. ]

Verify purchase and mass limits:
actual total_purchases: 402, purchase_limit: 1000
actual total_mass: 70, truck_mass_limit: 70

Page link：https//www.codepudding.com/Mobile/162813.html

Prev:Finding two "bounding" vertices of a given polygon w.r.t. a known (light source) point
Next:Why should we use std name space before functions of <algorithm> header and should not use it
  • Related

About Us:  Contact Us      Terms of Service       Privacy Policy

Copyright © 2010-2023，Powered By CodePudding