“I’m developing a system to create trips for delivery orders, and I’m facing challenges in implementing a fair distribution algorithm to allocate orders among trips based on cubes (weight) constraints. Here’s an overview of my system and the specific problem I’m encountering:

System Overview:

• The system aims to optimize the assignment of delivery orders to trips for efficient and to distribute fair numbers of orders based on no of stops and item cube.
• Trips are created for a specific date and have constraints such as maximum cube capacity (selected_cube) and maximum number of stops (selected_stops).
• Orders need to be distributed among trips in a fair and optimal manner, considering both cube constraints and no of stops.

Problem Statement:
I’m implementing a trip creation system in my application where I need to distribute orders among trips using a round-robin approach.

Example Scenario:
Let’s consider a scenario where there are 100 delivery orders with varying cubes, and we need to create trips for these orders. Each trip has a maximum weight capacity of 3000 cubes and can make up to 10 stops. How can we distribute these orders among trips to minimize the number of trips required while ensuring that no trip exceeds its weight capacity or stop limit? my current code is not populating a fair distribution of orders among trips when the total_selected_orders_cube is below 5000.

I have tried Round-robin and greedy approach unable to handle all the scenerios like small amount of selected orders.

Here’s a simplified version of my current implementation of round-robin:

    try {
    DB::beginTransaction();
    
    // Initialization code...

    $totalAssignedOrders = 0; // Track total assigned orders across all trips
    $tripIndices = []; // store trip indices for round-robin assignment
    $totalCreatedTrips = 0;
    
    for ($i = 0; $i < $requiredTrips && $totalAssignedOrders < $selectedOrdersCount; $i++){
        if (!isset($tripIndices[0]) || $tripIndices[0] >= $requiredTrips) {
            $tripIndices[0] = 0; // reset index if all trips are full
        }
    
        $trip = $this->tripService->createNewTrip($company_id, $schedule_date, 
        $defaultSelectedCubes, $defaultAssemblyTime);
    
        $unassignedOrders = []; // Store unassigned order IDs for this trip
    
        foreach ($request->input('orders') as $orderData) {
            $order = Orders::findOrFail($orderData['id']);
    
            // Check if the order already has a trip_id assigned
            if ($order->trip_id !== null) {
                continue;
            }
    
            $orderItems = $order->orderItems;
            $orderCube = $orderItems->sum('item_cube') ?? 0;
            $orderAssemblyTime = $orderItems->sum('assembly_time') ?? 0;
    
            if (
                $trip->assigned_cubes + $orderCube <= $defaultSelectedCubes &&
                $trip->assigned_assembly_time + $orderAssemblyTime <= $defaultAssemblyTime 
                &&
                $trip->no_of_stops < $defaultNoOfStops
            ) {
                $this->assignOrderToTrip($order, $trip, $schedule_date);
    
                $trip->assigned_cubes += $orderCube;
                $trip->assigned_assembly_time += $orderAssemblyTime;
                $trip->no_of_stops += 1;
                $trip->save();
    
                $totalAssignedOrders++; // Increment total assigned orders
            } else {
                $unassignedOrders[] = $order->id; // store only order ID for efficiency
            }
        }
    
        // Check if no orders were assigned to the newly created trip
        if (empty($unassignedOrders)) {
            continue; // Skip saving empty trips
        }
    
        $tripIndices[0]++; // increment trip index for round-robin
        $totalCreatedTrips++;
    }

    DB::commit();

    } catch (Exception $e) {
      // Exception handling code...
    }