Capacitated arc routing problem
ગણિતમાં, કેપેસિટેટેડ આર્ક રાઉટીંગ પ્રોબ્લેમ (સી. એ. આર. પી.) એ છે કે જે બરફ-પ્લાવર્સ, સ્ટ્રીટ સ્વીપિંગ મશીનો, અથવા શિયાળુ ગ્રિટર અથવા ક્ષમતાની મર્યાદાઓ સાથે અન્ય વાસ્તવિક દુનિયાની વસ્તુઓનું પ્રતિનિધિત્વ કરતા આલેખ સાથે આગળ વધતા પદાર્થો માટે ક્ષમતાની મર્યાદાઓને ધ્યાનમાં રાખીને દિશાહીન ધાર અને નિર્દેશિત ચાપ સાથે મિશ્ર ગ્રાફના ઓછામાં ઓછા ગ્રાફ/મુસાફરી અંતર સાથે ટૂંકી મુલાકાત શોધવાનું છે. આ પ્રતિબંધ વાહન કેન્દ્રીય ડેપોથી કેટલા સમય સુધી દૂર છે, અથવા કુલ અંતરની મુસાફરી અથવા વિવિધ વજન પરિબળો સાથે બંનેના સંયોજન માટે લાદવામાં આવી શકે છે. એન્જલ કોર્બેરન અને ગિલ્બર્ટ લાપોર્ટેના પુસ્તક આર્ક રાઉટીંગઃ પ્રોબ્લેમ્સ, મેથડ્સ એન્ડ એપ્લિકેશન્સમાં વર્ણવેલ સીએઆરપીની ઘણી જુદી જુદી ભિન્નતાઓ છે. સી. એ. આર. પી. ને ઉકેલવામાં ટૂંકો માર્ગ અસરકારક રીતે શોધવા માટે આલેખ સિદ્ધાંત, ચાપ રૂટીંગ, કામગીરી સંશોધન અને ભૌગોલિક રૂટીંગ અલ્ગોરિધમ્સનો અભ્યાસ સામેલ છે. સી. એ. આર. પી. એ એન. પી.-હાર્ડ આર્ક રાઉટીંગ સમસ્યા છે. સી. એ. આર. પી. ને બહિર્મુખ પત્થરો સહિત સંયુક્ત ઓપ્ટિમાઇઝેશન સાથે ઉકેલી શકાય છે. લાર્જ-સ્કેલ કેપેસિટેટેડ આર્ક રાઉટીંગ પ્રોબ્લેમ (એલ. એસ. સી. એ. આર. પી.) એ કેપેસિટેટેડ આર્ક રાઉટીંગ સમસ્યાનો એક પ્રકાર છે જે સેંકડો ધાર અને ગાંઠોને લાગુ પડે છે જેથી મોટા જટિલ વાતાવરણનું વાસ્તવિક અનુકરણ અને નમૂના તૈયાર કરી શકાય. સંદર્ભો આલેખ સિદ્ધાંત