mfsolver.cpp

研究多个dc对应多个dealer时得物流配送系统的优化问题

    y1 = d.y;

    double dx = x1 - x0, dy = y1 - y0;
    return 69*1.14*sqrt(dx*dx + dy*dy);
}

void MFSolver:: GetCostStandard
    (
        const Path &p, 
        double &s_cpm, 
        double &s_cph, 
        double &l_cpm, 
        double &l_cps, 
        double &storage_cost, 
        double &router_cost
    ) const
{
    const RDC &r = RDCSet[p.stops.front()];
    s_cpm = r.s_cpm;
    s_cph = r.s_cph;
    l_cpm = r.l_cpm;
    l_cps = r.l_cps;
    storage_cost = r.storage_cost;
    router_cost = r.router_cost;
}


double MFSolver::GetTotalCost(const Path &p, const Dealer &d) const
{
    /**********************************************************************/
    /*                   声明局部变量并对它们进行初始化                   */
    /**********************************************************************/
    double res = 0.0;

    double demand = 0.0;

    bool is_short = true;

    double s_cpm        = 0.0; // 短程每英里开销
    double s_cph        = 0.0; // 短程每小时开销
    double l_cpm        = 0.0; // 长途每英里开销
    double l_cps        = 0.0; // 长途每站点开销
    double storage_cost = 0.0;
    double router_cost  = 0.0;

    double x0  = 0.0;
    double y0  = 0.0;
    double x1  = 0.0;
    double y1  = 0.0;
    double dis = 0.0;

    /**********************************************************************/
    /*  计算加上这个新的节点后的总需求,如果超载了,则返回一个足够大的费用  */
    /**********************************************************************/
    demand = p.demand + d.demand;
    if (demand > max_load)
    {
        return 10e40;
    }

    /**********************************************************************/
    /*         读取收费标准(该标准随路径起始节点RDC的不同而不同)          */
    /**********************************************************************/
    GetCostStandard(p,s_cpm,s_cph,l_cpm,l_cps, storage_cost, router_cost);

    /**********************************************************************/
    /*   计算增加新节点后该路径的总长度是否超过了短程和长途路程的分界线   */
    /**********************************************************************/
    is_short = ((p.length + GetLength(p,d)) <= short_threshold);

    /**********************************************************************/
    /*                    计算从起点运输到原终点的费用                    */
    /**********************************************************************/
    x0 = RDCSet[p.stops.front()].x;
    y0 = RDCSet[p.stops.front()].y;
    if(p.stops.size() > 1)
    {
        list<int>::const_iterator it = p.stops.begin();

        for (++it; it != p.stops.end(); ++it)
        {
            const Dealer &d = dealerSet[*it];

            x1 = d.x;
            y1 = d.y;
            dis = 69*1.14*sqrt((x1-x0)*(x1-x0) + (y1-y0)*(y1-y0));

            if (is_short)
            {
                res += dis * s_cpm * ((demand < min_load)?min_load:demand);
            }
            else
            {
                res += dis * l_cpm * ((demand < min_load)?min_load:demand);
            }

            demand -= d.demand;
            x0 = x1;
            y0 = y1;
        }
    }

    /**********************************************************************/
    /*                     计算从原终点到新终点的费用                     */
    /**********************************************************************/
    x1 = d.x;
    y1 = d.y;
    dis = 69*1.14*sqrt((x1-x0)*(x1-x0) + (y1-y0)*(y1-y0));

    if (is_short)
    {
        res += dis * s_cpm * ((demand < min_load)?min_load:demand);
    }
    else
    {
        res += dis * l_cpm * ((demand < min_load)?min_load:demand);
    }

    /**********************************************************************/
    /*                  计算因增加该节点而增加的仓储成本                  */
    /**********************************************************************/
    res += storage_cost * d.demand;

    /**********************************************************************/
    /*如果这是一条从某个RDC上新开辟的线路，则还需要加上增加这条线路的成本 */
    /**********************************************************************/
    if(p.stops.size() == 1)
    {
        res += router_cost;
    }

    return res;
} 


double MFSolver::GetDiffCost(const Path &p, const Dealer &d) const
{
    return GetTotalCost(p,d) - p.cost;
}

double MFSolver::GetObjectiveValue(const Path &p, const Dealer &d) const
{
    return GetDiffCost(p,d)/d.demand;
}

void MFSolver::ExpandPath(Engine *ep, std::list<int> &candidateSet, bool useTimes)
{
    list<int>::iterator bestDealer = candidateSet.begin();
    list<Path>::iterator bestPath = pathSet.begin();
    double objv = GetObjectiveValue(*bestPath, dealerSet[*bestDealer]);

    list<int>::iterator id = candidateSet.begin();
    for ( ; id != candidateSet.end(); ++id)
    {// 寻找最优的扩展方案
        Dealer &d = dealerSet[*id];
        list<Path>::iterator ip = pathSet.begin();
        for ( ; ip != pathSet.end(); ++ip)
        {
            Path &p = *ip; 
            double o = GetObjectiveValue(p, d);
            if ( o < objv)
            {
                objv = o;
                bestDealer = id;
                bestPath = ip;
            }
        }
    }

    DrawPath(ep, *bestPath, dealerSet[*bestDealer]);

    if (bestPath->stops.size() == 1)
    {
        // 若最优方案是从地包商出发，则需要复制一份
        pathSet.push_back(*bestPath);

        Dealer &bd = dealerSet[*bestDealer];
        Path &bp = pathSet.back();
        double diffCost = GetDiffCost(bp, bd);
        bp.cost += diffCost;
        bp.demand += bd.demand;
        bp.distance = GetDistance(bp,bd);
        bp.length += GetLength(bp,bd);
        bp.stops.push_back(*bestDealer);

        if(useTimes)
        {
            for(int i = 1; i < bd.times; i++)
            {
                pathSet.push_back(bp);
            }
        }
    }
    else
    {
        Dealer &bd = dealerSet[*bestDealer];
        Path &bp = *bestPath;
        double diffCost = GetDiffCost(bp, bd);
        bp.cost += diffCost;
        bp.demand += bd.demand;
        bp.distance = GetDistance(bp,bd);
        bp.length += GetLength(bp,bd);
        bp.stops.push_back(*bestDealer);
    }

    // 从候选站点中删除已经添加的站点
    candidateSet.erase(bestDealer);

}

void  MFSolver::ComputeFlow(Engine *ep)
{
    int num = (int)candidateSet.size();
    while(candidateSet.size() > 0)
    {
        ExpandPath(ep, candidateSet);
    }

    list<int>::iterator id = addSet.begin();
    for ( ; id != addSet.end(); ++id)
    {
        Dealer &d = dealerSet[*id];
        d.demand = max_load;
    }
    
    num = (int)addSet.size();
    while(addSet.size() > 0)
    {
        ExpandPath(ep, addSet, true);
    }
}

void MFSolver::DrawPath(Engine *ep, const Path &p, const Dealer &d) const
{
    static cout = 0;

    int i = 0;  // loop control
    int RDCNo;  // RDC编号

    double x0;
    double y0;
    double x1;
    double y1;

    CString MatCmdLine;

    RDCNo = p.stops.front();

    if (p.stops.size() == 1)
    {
        x0 = RDCSet[p.stops.back()].x;
        y0 = RDCSet[p.stops.back()].y;
    }
    else
    {
        x0 = dealerSet[p.stops.back()].x;
        y0 = dealerSet[p.stops.back()].y;
    }

    x1 = d.x;
    y1 = d.y;

    /* 将线段分成若干段，每毫秒显示一段，产生动画效果 */
    for(i = 0; i < SEGMENT_COUNT; i++)
    {
        MatCmdLine.Format("plot([%f;%f],[%f;%f],'color',c%d);", x0+(x1-x0)*i/SEGMENT_COUNT,x0+(x1-x0)*(i+1)/SEGMENT_COUNT,y0+(y1-y0)*i/SEGMENT_COUNT,y0+(y1-y0)*(i+1)/SEGMENT_COUNT,RDCNo);
        engEvalString(ep, MatCmdLine);
        ::Sleep(1);
    }

/*
    MatCmdLine.Format("plot([%f;%f],[%f;%f],'color',c%d);", x0,x1,y0,y1,RDCNo);
    engEvalString(ep, MatCmdLine);

    cout = (cout+1)%20;

    if(cout == 0)
    {
        ::Sleep(1);
    }
*/
}